Start adding the supporting code to perform out-of-process allocator enumeration.

[delcypher]

Summary

This patch introduces the local portion (LocalObjectView) of the
ObjectView abstraction and demonstrates its use by modifying the
secondary allocator for out-of-process enumeration.

The ObjectView abstraction is an interface that tries to abstract away
the differences performing in-process and out-of-process operations so
that in-process and out-of-process enumeration can share the same
implementation.

This patch refers to but does not add the RemoteObjectView
implementation of the ObjectView abstraction which will be added
in later patches.

This patch is based on https://reviews.llvm.org/D50330 which provides
a complete implementation for all allocators but has been abandoned
due to difficulty of reviewing the code.

rdar://problem/45284065

[delcypher]

Drop now unused type_traits header.

[kcc]

OMG.

I sympathize with your problem, but the solution makes the code unreadable and unmaintainable.
The point of having templates is to avoid code like

if (ObjectView::IsLocal()) {

Also, if the change requires replacing

auto t = chunks_[i];

with the code below I can not accept such a change.

Header **header_ptr_addr = &(chunks_[i]);
// Copy header pointer into this process
typename ObjectView::template SmallAllocTy<Header *> header_ptr_view(
    header_ptr_addr);
Header *t = *(header_ptr_view.GetLocalAddress());

Is there a reasonable way to replace it with this?

auto t = Load(&chunks_[i]);

If not, you may need to find completely different way, e.g. not changing the allocator code at all and instead doing the introspection in an independent part of code.
Whenever the allocator data layout changes, you will have to change that code too, but with proper tests you will at least know when you need to do it.

[delcypher]

In D53975#1284314, @kcc wrote:

OMG.

I sympathize with your problem, but the solution makes the code unreadable and unmaintainable.
The point of having templates is to avoid code like

if (ObjectView::IsLocal()) {

That's not what the ObjectView (the template parameter) type does. The ObjectView abstraction let's its clients look at an object regardless of whether it exists in the current process or a remote process. The abstraction does not abstract away operations on the object.
It is the Object's job (in this case the allocator) to know how to perform operations on itself, whether that be in-process or out-of-process. This implies that the allocator has to handle performing operations on itself and this includes out-of-process operations. Trying to push
the knowledge of the peculiarities of a particular allocator into ObjectView type does not make sense from a software engineering perspective.

However there are things we could do to make this more aesthetically pleasing. For example we could make the EnsureSortedChunks() be a no-op when the allocator is instantiated with the ObjectView type for out-of-process enumeration.
Fundamentally however, the code path of in-process and out-of-process enumeration are similar but there are some divergences that have to be handled somewhere which is why you are seeing this ObjectView::IsLocal() guard.

Also, if the change requires replacing

auto t = chunks_[i];

with the code below I can not accept such a change.

Header **header_ptr_addr = &(chunks_[i]);
// Copy header pointer into this process
typename ObjectView::template SmallAllocTy<Header *> header_ptr_view(
    header_ptr_addr);
Header *t = *(header_ptr_view.GetLocalAddress());

Is there a reasonable way to replace it with this?

auto t = Load(&chunks_[i]);

Yes, but with a caveat. The type of t will not be Header* it will be LocalObjectView<Header*> for the in-process instantiation and RemoteObjectView<Header*, StackStorage> for the out-of-process.
The reason for this is that for the out-of-process case we need to manage the memory (allocate, copy into, and deallocate) for the object that is copied from a remote process. This is what the RemoteObjectView
object (not included in this patch) is doing.

However what we can do it provide an implicit conversion (like we do with llvm::cl::opt<int> today) so that can be treated as the type it represents (Header* in this case). Personally I'd prefer not to do the implicit conversion operation
because I prefer the programmer to be aware of the type they are working with (i.e. an ObjectView<Header*> and not a Header*) but I can see the appeal of the implicit conversion.

I'll make the change and let you take a look.

[kcc]

have you considered implementing this fully outside of the sanitizer allocator?
It might end up being much cleaner.

[delcypher]

• Simplify the way we make new instances of ObjectView<ObjectTy> by introducing a MakeView(...) function
• Add an implicit conversion operator to LocalObjectView<ObjectTy> so it can be implicitly converted to ObjectTy&. This allows us to simplify the code a bit.

[kubamracek]

In D53975#1284724, @kcc wrote:

have you considered implementing this fully outside of the sanitizer allocator?

Yes, but it would effectively be a downstream change which means longterm maintenance burden on us. We want to avoid that (the need for me or Dan to rush a fix whenever the allocator changes slightly upstream).

[delcypher]

Unguard consistency checks by rewriting them by using ObjectView interface.

[delcypher]

@kcc Please take another look at the patch. I have tried to address some of the issues you raised. I've removed one of the ObjectView::IsLocal() guards but the one around EnsureSortedChunks() remains.

There are various technical reasons why don't want to do this on the out-of-process path which I can explain if you really want. However could you explain something to me?

Why is EnsureSortedChunks() even called at all? I see nothing in the iteration code that would actually trigger a sort.
During the call to ForEachChunk(...) the allocator is also supposed to be locked so other threads won't be able to trigger a sort either. This suggests to me that the call to EnsureSortedChunks() is unnecessary, even on the in-process path. If we remove that then this ObjectView::IsLocal() guard issue just goes away.

[delcypher]

• Guard second check because it only holds when EnsureSortedChunks() has been called.
• Minor tweaks.

[delcypher]

Why is EnsureSortedChunks() even called at all? I see nothing in the iteration code that would actually trigger a sort.
During the call to ForEachChunk(...) the allocator is also supposed to be locked so other threads won't be able to trigger a sort either. This suggests to me that the call to EnsureSortedChunks() is unnecessary, even on the in-process path. If we remove that then this ObjectView::IsLocal() guard issue just goes away.

Okay I figured it out. It's the callback that could trigger a sort. The current callback implementations call things like GetUserBegin() which can eventually trigger a call in the allocator to GetBlockBeginFastLocked() which will try to sort the chunks.

[delcypher]

@kcc

In D53975#1284776, @kubamracek wrote:

In D53975#1284724, @kcc wrote:

have you considered implementing this fully outside of the sanitizer allocator?

Yes, but it would effectively be a downstream change which means longterm maintenance burden on us. We want to avoid that (the need for me or Dan to rush a fix whenever the allocator changes slightly upstream).

Just to add this. The patch you looked at during LLVMDev was effectively "implementing this fully outside of the sanitizer allocator". That patch had out-of-process variants of the important allocator methods and declared them elsewhere so they were only compiled for Darwin. You rightly rejected that patch (because it duplicated a bunch of allocator code) and requested we look at unifying the implementations. This patch is my best attempt at unifying the implementations. I personally think the approach in this patch is much better and I'm glad you pushed us to investigate implementing out-of-process enumeration in this way.

So we've seen both approaches and so we need to decide which has the better trade off for maintainability.

For what it's worth this allocator is the only allocator where the issue of having use ObjectView::IsLocal() guards actually comes up. None of the other allocators try to modify themselves during chunk enumeration. So ObjectView::IsLocal() guards won't appear anywhere else.

[delcypher]

Remove two const attributes that breaks the RemoteObjectView implementation (not up for review yet).

[delcypher]

@kcc Any more thoughts on this?

[kcc]

no new thoughts, sorry. The patch continues to horrify me.

[kubamracek]

Can you please be more specific about what exactly are you objecting against? We really want the code for the out-of-process enumeration to be part of compiler-rt, otherwise we'll be getting downstream failures forever. And in compiler-rt, the code belongs to the allocator.

We might be able to improve on this further, if you explain what specifically you don't like: The IsLocal checks are needed because the code modifies memory. We could change the function to have another bool argument that would specify whether modifications are allowed or not.

[krytarowski]

Is this out of process only to enumarate? Is there an option to support this through debugging interfaces and analysis of a program? I mean to inspect asanitized program from an external debugger(-like) program.

[kubamracek]

In D53975#1288203, @krytarowski wrote:

Is this out of process only to enumarate? Is there an option to support this through debugging interfaces and analysis of a program? I mean to inspect asanitized program from an external debugger(-like) program.

The goal of this patch is to exactly allow an external debugger-like program to analyze the heap. There's existing macOS tools (heap, leaks, malloc_history) that use the interface that we're trying to implement.

[krytarowski]

Interesting, are these tools open-source? I would be interested to port them to NetBSD.

[kubamracek]

They're not open source. The interface to them is at https://opensource.apple.com/source/Libc/Libc-498/include/malloc/malloc.h.

[george.karpenkov]

lib/sanitizer_common/sanitizer_allocator_secondary.h

284 ↗

(On Diff #172349)

I think writing
auto t = ObjectView::MakeView(&chunks_[i])
is considerably more clear.
@kcc Would that be better with you?

We can also do an implicit constructor and write

ObjectView t = &chunks_[i]

290 ↗

(On Diff #172349)

Cast seems to be the wrong operator here, why not * ?
Then we could write

CHECK_EQ(*t, *ObjectView::MakeView(&chunks_[i]))

[delcypher]

lib/sanitizer_common/sanitizer_allocator_secondary.h

290 ↗

(On Diff #172349)

I'm basically just using static_cast<Header*>() to trigger to the conversion operator to ObjectTy&.

I could also provide a operator*(). I'm just not convinced it's clearer.

We could also provide operator==. So that the check reads as CHECK_EQ(t, ObjectView::MakeView(&chunks_[i])).

The problem there though is that template instantiation will fail if the ObjectTy in LocalObjectView doesn't have an == operator. We could use std::enable_if to conditionally declare the operator only if ObjectTy has an == operator. The trouble with that is because C++ doesn't have concepts yet, actually writing this would be extremely messy.

[delcypher]

Simplify design even further at the expense of memory management.

[delcypher]

Remove clang-format whitespace change.

[krytarowski]

In D53975#1289005, @kubamracek wrote:

They're not open source. The interface to them is at https://opensource.apple.com/source/Libc/Libc-498/include/malloc/malloc.h.

It looks like mallinfo from GNU or similar and it looks like closely tied to Darwin internals, so it does not seem to be reusable by others.

[delcypher]

@kcc @kubamracek & I discussed this change some more and we've produced an even simpler patch at the expense being able to do good memory management in the out-of-process case.
Please take a look and let us know what you think.

[kcc]

(sorry, I have been distracted).
The first impression is that this seems manageable. Thank you for bearing with me.

Maybe, as a bike-shedding exercise, try to find a better name for ObjectMap

[delcypher]

In D53975#1291024, @krytarowski wrote:

In D53975#1289005, @kubamracek wrote:

They're not open source. The interface to them is at https://opensource.apple.com/source/Libc/Libc-498/include/malloc/malloc.h.

It looks like mallinfo from GNU or similar and it looks like closely tied to Darwin internals, so it does not seem to be reusable by others.

The complete implementation will be darwin specific. However the changes we will be making to the allocators themselves will be platform agnostic so it will be possible to build tools on top of this.

[delcypher]

@kcc

Maybe, as a bike-shedding exercise, try to find a better name for ObjectMap

Given that the ObjectMap abstraction doesn't necessarily deal with single objects having Object in the name isn't very helpful.
All the abstraction now does it map pointers from one address space into another while transparently handling the copying.

Based on those observations here are some other name ideas

• PointerMap
• AddressSpaceView (possibly shortened to AddrSpaceView). This name suggests renaming the Map(...) method to Load(...).
• VMView. This name suggests renaming the Map(...) method to Load(...).

Other suggestions are welcome.

[kcc]

AddressSpaceView::Load sounds great.
You can go further and rename Load to operator(), then declare a member

AddressSpaceView Load;

such that the code would look like

Load(chunks[i])

but that's up to you.

Please add comments and tests.
Are you planing to add the rest of the code to this change, or commit it separately? (either works)

[delcypher]

In D53975#1293500, @kcc wrote:

AddressSpaceView::Load sounds great.
You can go further and rename Load to operator(), then declare a member

AddressSpaceView Load;

such that the code would look like

Load(chunks[i])

but that's up to you.

If we make AddressSpaceView an instance member because it will change the data layout of the allocator (the out-of-process version of AddressSpaceView will not be zero sized, unlike the in-process version). This is something we cannot allow. However, we could make it a static member I suppose which won't affect data layout. I need to use this AddressSpaceView in other places outside of a class and I'm a little worried how it will look there. I'd rather stick with the Load method for now and apply your suggested transformation in later commits if it turns out to be necessary.

Please add comments and tests.
Are you planing to add the rest of the code to this change, or commit it separately? (either works)

There are many parts to this change which I'm going to have to land as separate commits. Here's my rough plan

1. Put up a change for each allocator change required for ForEachChunk(). At this point we won't introduce the out-of-process version of AddressSpaceView and will rely on the existing allocator unit tests. If there are missing allocator unit tests I will add them. This might seem odd choice but the out-of-process version of AddressSpaceView simply isn't ready yet (the requirements have changed which my old implementation cannot meet). However I know what the allocator changes will need to be so I can have those sitting in the review pipeline while I implement the out-of-process version of AddressSpaceView.

2. Start a review sketching a design for how to implement LSanChunkView and ASanChunkView out-of-process. This is another major part of the work because being able to do ForEachChunk out-of-process isn't useful on its own. We need a way to know what the state of each enumerated chunk is.

3. Put up for review an out-of-process of AddressSpaceView. This will include unit tests to make sure the allocator can be instantiated with this other type and that enumeration still works.

4. Put up for review the Darwin specific code that will use the new out-of-process interfaces. This will include a Darwin only "system test" that exercises all the newly introduced code.

I'm going to tweak this change a bit so that it is a change for the Secondary allocator. Separate changes will follow.

[kcc]

I'm puzzled.
Why would you make AddressSpaceView non-zero-sized given that Load is a static member function?

I would like to see a test that uses a non-default implementation of AddressSpaceView.

[delcypher]

In D53975#1296359, @kcc wrote:

I'm puzzled.
Why would you make AddressSpaceView non-zero-sized given that Load is a static member function?

Sorry. I was thinking of the old implementation and not the new implementation (I shouldn't reply when I'm really tired). Yes, you're right all implementations of AddressSpaceView will be zero-sized.

I would like to see a test that uses a non-default implementation of AddressSpaceView.

Yes I will be landing tests in two forms.

• Unit tests that check on all platforms that it's possible to instantiate the allocator and use it with RemoteAddressSpaceView (these won't actually launch a separate process).
• A lit test that that acts like one of Darwin's memory analysis tools by enumerating all the allocations of another process that is using ASan.

[delcypher]

In D53975#1296826, @delcypher wrote:

In D53975#1296359, @kcc wrote:

I'm puzzled.
Why would you make AddressSpaceView non-zero-sized given that Load is a static member function?

Sorry. I was thinking of the old implementation and not the new implementation (I shouldn't reply when I'm really tired). Yes, you're right all implementations of AddressSpaceView will be zero-sized.

Okay I just checked. Unfortunately your idea to have an instance of AddressSpaceView as a member and add operator() isn't going to work. It seems C++ does not allow zero sized classes. Even a class with zero members have to be at least 1 byte in size apparently.
This implies that adding AddressSpaceView as a member could change the data layout which is a deal breaker for us. So for now we'll have to do without the syntactic sugar for now. I'll upload a new patch soon.

Just in case you were curious here's an example that shows empty classes don't have zero size.

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

using uptr = uintptr_t;

struct LocalAddressSpaceView {
  template <typename T>
  static T *Load(T *target_address, uptr num_elements = 1) {
    return target_address;
  }

  LocalAddressSpaceView() {
    static_assert(sizeof(LocalAddressSpaceView) == 1, "Must be zero sized");
  }
};

struct Foo {
  LocalAddressSpaceView a;
  LocalAddressSpaceView b;
};

int main() {
  Foo foo;
  printf("Foo: 0x%" PRIx64 "\n", reinterpret_cast<uintptr_t>(&foo));
  // Note &(foo.a) != &(foo.b);
  printf("Foo.a: 0x%" PRIx64 "\n", reinterpret_cast<uintptr_t>(&(foo.a)));
  printf("Foo.b: 0x%" PRIx64 "\n", reinterpret_cast<uintptr_t>(&(foo.b)));
  return 0;
}

[delcypher]

• s/ObjectView/AddressSpaceView/.
• More comments.
• Rewrite commit description.
• Move LocalAddressSpaceView into its own header file for consumption by other parts of the code in later patches.

[delcypher]

@kcc is this version of the patch good enough to land? As noted earlier.

• We will land unit tests for each allocator once we land RemoteAddressSpaceView.
• Changes to the other allocators will come as separate patches.

[kcc]

LGTM
You may still replace AddressSpaceView::Load with Load by implementing a one-line function inside this class. Up to you.

[delcypher]

In D53975#1298813, @kcc wrote:

LGTM
You may still replace AddressSpaceView::Load with Load by implementing a one-line function inside this class. Up to you.

Thanks. I'd rather not do this right now. I'm worried that as I re-implement all my work using the new interface, that I will discover somewhere minor tweaks are required. Once all the out-of-process enumeration pieces have landed I'll be happy to a one-line function to make the syntax shorter.

compiler-rt/trunk/lib/sanitizer_common/CMakeLists.txt

set(SANITIZER_IMPL_HEADERS
   sanitizer_interceptors_ioctl_netbsd.inc
   sanitizer_interface_internal.h
   sanitizer_internal_defs.h
   sanitizer_lfstack.h
   sanitizer_libc.h
   sanitizer_libignore.h
   sanitizer_linux.h
   sanitizer_list.h
+  sanitizer_local_address_space_view.h
   sanitizer_mac.h
   sanitizer_malloc_mac.inc
   sanitizer_mutex.h
   sanitizer_persistent_allocator.h
   sanitizer_placement_new.h
   sanitizer_platform.h
   sanitizer_platform_interceptors.h
   sanitizer_platform_limits_netbsd.h

compiler-rt/trunk/lib/sanitizer_common/sanitizer_allocator.h

 //===-- sanitizer_allocator.h -----------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Specialized memory allocator for ThreadSanitizer, MemorySanitizer, etc.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef SANITIZER_ALLOCATOR_H
 #define SANITIZER_ALLOCATOR_H
 
-#include "sanitizer_internal_defs.h"
 #include "sanitizer_common.h"
+#include "sanitizer_internal_defs.h"
+#include "sanitizer_lfstack.h"
 #include "sanitizer_libc.h"
 #include "sanitizer_list.h"
+#include "sanitizer_local_address_space_view.h"
 #include "sanitizer_mutex.h"
-#include "sanitizer_lfstack.h"
 #include "sanitizer_procmaps.h"
 
 namespace __sanitizer {
 
 // Allows the tools to name their allocations appropriately.
 extern const char *PrimaryAllocatorName;
 extern const char *SecondaryAllocatorName;
 

compiler-rt/trunk/lib/sanitizer_common/sanitizer_allocator_secondary.h

 #else
 typedef LargeMmapAllocatorPtrArrayDynamic DefaultLargeMmapAllocatorPtrArray;
 #endif
 
 // This class can (de)allocate only large chunks of memory using mmap/unmap.
 // The main purpose of this allocator is to cover large and rare allocation
 // sizes not covered by more efficient allocators (e.g. SizeClassAllocator64).
 template <class MapUnmapCallback = NoOpMapUnmapCallback,
-          class PtrArrayT = DefaultLargeMmapAllocatorPtrArray>
+          class PtrArrayT = DefaultLargeMmapAllocatorPtrArray,
+          class AddressSpaceView = LocalAddressSpaceView>
 class LargeMmapAllocator {
  public:
   void InitLinkerInitialized() {
     page_size_ = GetPageSizeCached();
     chunks_ = reinterpret_cast<Header**>(ptr_array_.Init());
   }
 
   void Init() {
void *GetBlockBegin(const void *ptr) {
     CHECK_LE(nearest_chunk, p);
     if (h->map_beg + h->map_size <= p)
       return nullptr;
     return GetUser(h);
   }
 
   void EnsureSortedChunks() {
     if (chunks_sorted_) return;
-    Sort(reinterpret_cast<uptr *>(chunks_), n_chunks_);
+    Header **chunks = AddressSpaceView::Load(chunks_, n_chunks_);
+    Sort(reinterpret_cast<uptr *>(chunks), n_chunks_);
     for (uptr i = 0; i < n_chunks_; i++)
-      chunks_[i]->chunk_idx = i;
+      AddressSpaceView::Load(chunks[i])->chunk_idx = i;
     chunks_sorted_ = true;
   }
 
   // This function does the same as GetBlockBegin, but is much faster.
   // Must be called with the allocator locked.
   void *GetBlockBeginFastLocked(void *ptr) {
     mutex_.CheckLocked();
     uptr p = reinterpret_cast<uptr>(ptr);
public:
   void ForceUnlock() {
     mutex_.Unlock();
   }
 
   // Iterate over all existing chunks.
   // The allocator must be locked when calling this function.
   void ForEachChunk(ForEachChunkCallback callback, void *arg) {
     EnsureSortedChunks();  // Avoid doing the sort while iterating.
+    Header **chunks = AddressSpaceView::Load(chunks_, n_chunks_);
     for (uptr i = 0; i < n_chunks_; i++) {
-      auto t = chunks_[i];
+      Header *t = chunks[i];
       callback(reinterpret_cast<uptr>(GetUser(t)), arg);
       // Consistency check: verify that the array did not change.
-      CHECK_EQ(chunks_[i], t);
-      CHECK_EQ(chunks_[i]->chunk_idx, i);
+      CHECK_EQ(chunks[i], t);
+      CHECK_EQ(AddressSpaceView::Load(chunks[i])->chunk_idx, i);
     }
   }
 
  private:
   struct Header {
     uptr map_beg;
     uptr map_size;
     uptr size;
private:
   PtrArrayT ptr_array_;
   uptr n_chunks_;
   bool chunks_sorted_;
   struct Stats {
     uptr n_allocs, n_frees, currently_allocated, max_allocated, by_size_log[64];
   } stats;
   StaticSpinMutex mutex_;
 };
-

compiler-rt/trunk/lib/sanitizer_common/sanitizer_local_address_space_view.h

+//===-- sanitizer_local_address_space_view.h --------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// `LocalAddressSpaceView` provides the local (i.e. target and current address
+// space are the same) implementation of the `AddressSpaveView` interface which
+// provides a simple interface to load memory from another process (i.e.
+// out-of-process)
+//
+// The `AddressSpaveView` interface requires that the type can be used as a
+// template parameter to objects that wish to be able to operate in an
+// out-of-process manner. In normal usage, objects are in-process and are thus
+// instantiated with the `LocalAddressSpaceView` type. This type is used to
+// load any pointers in instance methods. This implementation is effectively
+// a no-op. When an object is to be used in an out-of-process manner it is
+// instansiated with the `RemoteAddressSpaceView` type.
+//
+// By making `AddressSpaceView` a template parameter of an object, it can
+// change its implementation at compile time which has no run time overhead.
+// This also allows unifying in-process and out-of-process code which avoids
+// code duplication.
+//
+//===----------------------------------------------------------------------===//
+#ifndef SANITIZER_LOCAL_ADDRES_SPACE_VIEW_H
+#define SANITIZER_LOCAL_ADDRES_SPACE_VIEW_H
+
+namespace __sanitizer {
+struct LocalAddressSpaceView {
+  // Load memory `sizeof(T) * num_elements` bytes of memory
+  // from the target process (always local for this implementation)
+  // starting at address `target_address`. The local copy of
+  // this memory is returned as a pointer. It is guaranteed that
+  //
+  // * That the function will always return the same value
+  //   for a given set of arguments.
+  // * That the memory returned is writable and that writes will persist.
+  //
+  // The lifetime of loaded memory is implementation defined.
+  template <typename T>
+  static T *Load(T *target_address, uptr num_elements = 1) {
+    // The target address space is the local address space so
+    // nothing needs to be copied. Just return the pointer.
+    return target_address;
+  }
+};
+}  // namespace __sanitizer
+
+#endif