[IRMemoryMap] Fix the alignment adjustment in Malloc

[vsk]

Summary

This prevents Malloc from allocating the same chunk of memory twice, as
a byproduct of an alignment adjustment which gave the client access to
unallocated memory.

Prior to this patch, the newly-added test failed with:

$ lldb-test ir-memory-map ... ir-memory-map-overlap1.test
Command: malloc(size=8, alignment=16)
Malloc: address = 0x1000cd000
Command: malloc(size=16, alignment=8)
Malloc: address = 0x1000cd010
Command: malloc(size=64, alignment=32)
Malloc: address = 0x1000cd020
Command: malloc(size=1, alignment=8)
Malloc: address = 0x1000cd060
Command: malloc(size=64, alignment=32)
Malloc: address = 0x1000cd080
Command: malloc(size=64, alignment=8)
Malloc: address = 0x1000cd0b0
Malloc error: overlapping allocation detected, previous allocation at [0x1000cd080, 0x1000cd0c0)

I don't see anything controversial here (in fact Jim lgtm'd part of this patch off-list), but as this is unfamiliar territory for me I think it'd help to have a proper review. Depends on D47508.

[vsk]

• Don't insert extra padding bytes when alignment = 1.
• + Lang

[lhames]

LGTM.

I haven't looked at process memory management. How hard would your FIXME be to implement?

• Lang.

[labath]

I don't know much about IRMemoryMap myself, but this does seem uncontroversial. Nonetheless, I did manage to find something to rip into. :D

source/Expression/IRMemoryMap.cpp

311–315

allocation_size = llvm::alignTo(size, alignment)

323–324

I think this should be just allocation_size += alignment -1. The subsequent realignment cannot eat more than alignment-1 bytes.

[vsk]

In D47551#1117086, @lhames wrote:

LGTM.

I haven't looked at process memory management. How hard would your FIXME be to implement?

After looking at this more carefully, I think the FIXME makes a bad prescription. It's based on the assumption that each platform-specific allocator makes use of an efficient API to make aligned allocations. This doesn't generally seem to be true, because the platform-specific allocators rely on mmap().

A better alternative might be to add a new API, AllocatedMemoryCache::AllocateAlignedMemory(size, alignment). You could implement an alignment-aware allocator here, say, by splitting up free memory into a list of buckets (one list per alignment). Next, you could surface the API from Process, provided there's a fallback strategy when the allocated memory cache is disabled.

One caveat to all of this is that it might not be worth doing unless fragmentation-related overhead is identified as a bottleneck.

I'll remove the FIXME.

[vsk]

• Address Pavel's feedback, remove a questionable FIXME.

lit/Expr/Inputs/ir-memory-map-basic.test

+malloc 0 1
+malloc 1 1
+
+malloc 2 1
+malloc 2 2
+malloc 2 4
+
+malloc 3 1
+malloc 3 2
+malloc 3 4
+
+malloc 128 1
+malloc 128 2
+malloc 128 4
+malloc 128 128
+
+malloc 2048 1
+malloc 2048 2
+malloc 2048 4
+
+malloc 3968 1
+malloc 3968 2
+malloc 3968 4
+
+malloc 0 1

lit/Expr/Inputs/ir-memory-map-overlap1.test

+malloc 8 16
+malloc 16 8
+malloc 64 32
+malloc 1 8
+malloc 64 32
+malloc 64 8
+malloc 1024 32
+malloc 1 16
+malloc 8 16
+malloc 1024 16
 No newline at end of file

lit/Expr/TestIRMemoryMap.test

 # RUN: %cxx %p/Inputs/call-function.cpp -g -o %t
-# RUN: lldb-test ir-memory-map %t %s
-
-malloc 0 1
-malloc 1 1
-
-malloc 2 1
-malloc 2 2
-malloc 2 4
-
-malloc 3 1
-malloc 3 2
-malloc 3 4
-
-malloc 128 1
-malloc 128 2
-malloc 128 4
-malloc 128 128
-
-malloc 2048 1
-malloc 2048 2
-malloc 2048 4
-
-malloc 3968 1
-malloc 3968 2
-malloc 3968 4
-
-malloc 0 1
+# RUN: lldb-test ir-memory-map %t %S/Inputs/ir-memory-map-basic.test
+# RUN: lldb-test ir-memory-map %t %S/Inputs/ir-memory-map-overlap1.test

source/Expression/IRMemoryMap.cpp

lldb::addr_t IRMemoryMap::Malloc(size_t size, uint8_t alignment,
   lldb_private::Log *log(
       lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_EXPRESSIONS));
   error.Clear();
 
   lldb::ProcessSP process_sp;
   lldb::addr_t allocation_address = LLDB_INVALID_ADDRESS;
   lldb::addr_t aligned_address = LLDB_INVALID_ADDRESS;
 
-  size_t alignment_mask = alignment - 1;
   size_t allocation_size;
 
-  if (size == 0)
+  if (size == 0) {
+    // FIXME: Malloc(0) should either return an invalid address or assert, in
+    // order to cut down on unnecessary allocations.
     allocation_size = alignment;
-  else
-    allocation_size = (size & alignment_mask)
-                          ? ((size + alignment) & (~alignment_mask))
-                          : size;
+  } else {
+    // Round up the requested size to an aligned value.
+    allocation_size = llvm::alignTo(size, alignment);
+
+    // The process page cache does not see the requested alignment. We can't
+    // assume its result will be any more than 1-byte aligned. To work around
+    // this, request `alignment - 1` additional bytes.
+    allocation_size += alignment - 1;
+  }
 
   switch (policy) {
   default:
     error.SetErrorToGenericError();
     error.SetErrorString("Couldn't malloc: invalid allocation policy");
     return LLDB_INVALID_ADDRESS;
   case eAllocationPolicyHostOnly:
     allocation_address = FindSpace(allocation_size);
     if (allocation_address == LLDB_INVALID_ADDRESS) {
       error.SetErrorToGenericError();
       error.SetErrorString("Couldn't malloc: address space is full");
       return LLDB_INVALID_ADDRESS;
     }
     break;