[SectionMemoryManager] Make better use of virtual memory

[loladiro]

Summary

On Windows, the allocation granularity can be significantly larger than a page (64K), so with many small objects, just clearing the FreeMem list rapidly leaks quite a bit of virtual memory space (if not rss). Fix that by only removing those parts of the FreeMem blocks that overlap pages for which we are applying memory permissions, rather than dropping the FreeMem blocks entirely.

[loladiro]

Jameson Nash points out to me that on windows you're not allowed to pass ranges that straddle allocation domains to it's version of mprotect, so I'll update the code to take that into account.

[loladiro]

Updated to take into account that we shouldn't merge things across reservation boundaries.
Instead, have a free block keep a reference to any pending block that may be before it
(in the same allocation) and updating that as we go along.

[loladiro]

Remove a method used in the first version that is no longer used now.

[lhames]

This sounds great.

I don't think we want to change the operations on MemoryBlock though - I'd rather see SectionMemoryManager create new MemoryBlocks representing the ranges you want to change permissions on.

[loladiro]

I added trimMemoryBlock to Memory because it depends on the system Page size, but later realized that Process already exposes that, so I would be happy to just make that a static function in the SectionMemoryManager.

[loladiro]

Make trimBlockToPageSize a static in SectionMemoryManager rather than a new
static member of Memory.

[loladiro]

Fix accidental inclusion of a previous commit in the diff which is already on trunk.

[loladiro]

Used indices rather than pointers into the array, because those can get
invalidated if you're not careful.

[loladiro]

@lhames, does this look ok now?

[lhames]

LGTM. Thanks Keno!

llvm/trunk/include/llvm/ExecutionEngine/SectionMemoryManager.h

public:
   /// Some platforms with separate data cache and instruction cache require
   /// explicit cache flush, otherwise JIT code manipulations (like resolved
   /// relocations) will get to the data cache but not to the instruction cache.
   ///
   /// This method is called from finalizeMemory.
   virtual void invalidateInstructionCache();
 
 private:
+  struct FreeMemBlock {
+    // The actual block of free memory
+    sys::MemoryBlock Free;
+    // If there is a pending allocation from the same reservation right before
+    // this block, store it's index in PendingMem, to be able to update the
+    // pending region if part of this block is allocated, rather than having to
+    // create a new one
+    unsigned PendingPrefixIndex;
+  };
+
   struct MemoryGroup {
-      // PendingMem contains all allocated memory blocks
-      // which have not yet had their permissions set. Note
-      // that this tracks memory blocks that have been given to
-      // this memory manager by the system, not those
-      // given out to the user. In particular, the memory manager
-      // will give out subblocks of these MemoryBlocks in response
-      // to user requests. We track which subblocks have not beeen
-      // given out yet in `FreeMem`.
-      SmallVector<sys::MemoryBlock, 16> PendingMem;
-      SmallVector<sys::MemoryBlock, 16> FreeMem;
+    // PendingMem contains all blocks of memory (subblocks of AllocatedMem)
+    // which have not yet had their permissions applied, but have been given
+    // out to the user. FreeMem contains all block of memory, which have
+    // neither had their permissions applied, nor been given out to the user.
+    SmallVector<FreeMemBlock, 16> FreeMem;
 
-      // All allocated memory blocks that have had their permissions
-      // set (i.e. that have been finalized). Because of this, we may
-      // not give out subblocks of this memory to the user anymore,
-      // even if those subblocks have not been previously given out.
-      SmallVector<sys::MemoryBlock, 16> AllocatedMem;
+    // All memory blocks that have been requested from the system
 
-      sys::MemoryBlock Near;
   };
 
   uint8_t *allocateSection(MemoryGroup &MemGroup, uintptr_t Size,
                            unsigned Alignment);
 
   std::error_code applyMemoryGroupPermissions(MemoryGroup &MemGroup,
                                               unsigned Permissions);
 
   MemoryGroup CodeMem;
   MemoryGroup RWDataMem;
   MemoryGroup RODataMem;
 };
 
 }
 
 #endif // LLVM_EXECUTION_ENGINE_SECTION_MEMORY_MANAGER_H
-

llvm/trunk/lib/ExecutionEngine/SectionMemoryManager.cpp

 // This file implements the section-based memory manager used by the MCJIT
 // execution engine and RuntimeDyld
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Config/config.h"
 #include "llvm/ExecutionEngine/SectionMemoryManager.h"
 #include "llvm/Support/MathExtras.h"
+#include "llvm/Support/Process.h"
 
 namespace llvm {
 
 uint8_t *SectionMemoryManager::allocateDataSection(uintptr_t Size,
                                                    unsigned Alignment,
                                                    unsigned SectionID,
                                                    StringRef SectionName,
                                                    bool IsReadOnly) {
uint8_t *SectionMemoryManager::allocateSection(MemoryGroup &MemGroup,
 
   assert(!(Alignment & (Alignment - 1)) && "Alignment must be a power of two.");
 
   uintptr_t RequiredSize = Alignment * ((Size + Alignment - 1)/Alignment + 1);
   uintptr_t Addr = 0;
 
   // Look in the list of free memory regions and use a block there if one
   // is available.
-  for (sys::MemoryBlock &MB : MemGroup.FreeMem) {
-    if (MB.size() >= RequiredSize) {
-      Addr = (uintptr_t)MB.base();
-      uintptr_t EndOfBlock = Addr + MB.size();
+  for (FreeMemBlock &FreeMB : MemGroup.FreeMem) {
+    if (FreeMB.Free.size() >= RequiredSize) {
+      Addr = (uintptr_t)FreeMB.Free.base();
+      uintptr_t EndOfBlock = Addr + FreeMB.Free.size();
       // Align the address.
       Addr = (Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1);
-      // Store cutted free memory block.
-      MB = sys::MemoryBlock((void *)(Addr + Size), EndOfBlock - Addr - Size);
+
+      if (FreeMB.PendingPrefixIndex == (unsigned)-1) {
+        // The part of the block we're giving out to the user is now pending
+        MemGroup.PendingMem.push_back(sys::MemoryBlock((void *)Addr, Size));
+
+        // Remember this pending block, such that future allocations can just
+        // modify it rather than creating a new one
+        FreeMB.PendingPrefixIndex = MemGroup.PendingMem.size() - 1;
+      } else {
+        sys::MemoryBlock &PendingMB = MemGroup.PendingMem[FreeMB.PendingPrefixIndex];
+        PendingMB = sys::MemoryBlock(PendingMB.base(), Addr + Size - (uintptr_t)PendingMB.base());
+      }
+
+      // Remember how much free space is now left in this block
+      FreeMB.Free = sys::MemoryBlock((void *)(Addr + Size), EndOfBlock - Addr - Size);
       return (uint8_t*)Addr;
     }
   }
 
   // No pre-allocated free block was large enough. Allocate a new memory region.
   // Note that all sections get allocated as read-write.  The permissions will
   // be updated later based on memory group.
   //
uint8_t *SectionMemoryManager::allocateSection(MemoryGroup &MemGroup,
   if (ec) {
     // FIXME: Add error propagation to the interface.
     return nullptr;
   }
 
   // Save this address as the basis for our next request
   MemGroup.Near = MB;
 
-  MemGroup.PendingMem.push_back(MB);
+  // Remember that we allocated this memory
+  MemGroup.AllocatedMem.push_back(MB);
   Addr = (uintptr_t)MB.base();
   uintptr_t EndOfBlock = Addr + MB.size();
 
   // Align the address.
   Addr = (Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1);
 
+  // The part of the block we're giving out to the user is now pending
+  MemGroup.PendingMem.push_back(sys::MemoryBlock((void *)Addr, Size));
+
   // The allocateMappedMemory may allocate much more memory than we need. In
   // this case, we store the unused memory as a free memory block.
   unsigned FreeSize = EndOfBlock-Addr-Size;
-  if (FreeSize > 16)
-    MemGroup.FreeMem.push_back(sys::MemoryBlock((void*)(Addr + Size), FreeSize));
+  if (FreeSize > 16) {
+    FreeMemBlock FreeMB;
+    FreeMB.Free = sys::MemoryBlock((void*)(Addr + Size), FreeSize);
+    FreeMB.PendingPrefixIndex = (unsigned)-1;
+    MemGroup.FreeMem.push_back(FreeMB);
+  }
 
   // Return aligned address
   return (uint8_t*)Addr;
 }
 
 bool SectionMemoryManager::finalizeMemory(std::string *ErrMsg)
 {
   // FIXME: Should in-progress permissions be reverted if an error occurs?
   std::error_code ec;
 
-  // Don't allow free memory blocks to be used after setting protection flags.
-  CodeMem.FreeMem.clear();
-
   // Make code memory executable.
   ec = applyMemoryGroupPermissions(CodeMem,
                                    sys::Memory::MF_READ | sys::Memory::MF_EXEC);
   if (ec) {
     if (ErrMsg) {
       *ErrMsg = ec.message();
     }
     return true;
bool SectionMemoryManager::finalizeMemory(std::string *ErrMsg)
 
   // Read-write data memory already has the correct permissions
 
   // Some platforms with separate data cache and instruction cache require
   // explicit cache flush, otherwise JIT code manipulations (like resolved
   // relocations) will get to the data cache but not to the instruction cache.
   invalidateInstructionCache();
 
-  // Now, remember that we have successfully applied the permissions to avoid
-  // having to apply them again.
-  CodeMem.AllocatedMem.append(CodeMem.PendingMem.begin(),CodeMem.PendingMem.end());
-  CodeMem.PendingMem.clear();
+  return false;
+}
 
-  RODataMem.AllocatedMem.append(RODataMem.PendingMem.begin(),RODataMem.PendingMem.end());
-  RODataMem.PendingMem.clear();
+static sys::MemoryBlock trimBlockToPageSize(sys::MemoryBlock M) {
+  static const size_t PageSize = sys::Process::getPageSize();
 
-  return false;
+  size_t StartOverlap =
+      (PageSize - ((uintptr_t)M.base() % PageSize)) % PageSize;
+
+  size_t TrimmedSize = M.size();
+  TrimmedSize -= StartOverlap;
+  TrimmedSize -= TrimmedSize % PageSize;
+
+  sys::MemoryBlock Trimmed((void *)((uintptr_t)M.base() + StartOverlap), TrimmedSize);
+
+  assert(((uintptr_t)Trimmed.base() % PageSize) == 0);
+  assert((Trimmed.size() % PageSize) == 0);
+  assert(M.base() <= Trimmed.base() && Trimmed.size() <= M.size());
+
+  return Trimmed;
 }
 
+
 std::error_code
 SectionMemoryManager::applyMemoryGroupPermissions(MemoryGroup &MemGroup,
                                                   unsigned Permissions) {
-
   for (sys::MemoryBlock &MB : MemGroup.PendingMem)
     if (std::error_code EC = sys::Memory::protectMappedMemory(MB, Permissions))
       return EC;
 
+  MemGroup.PendingMem.clear();
+
+  // Now go through free blocks and trim any of them that don't span the entire
+  // page because one of the pending blocks may have overlapped it.
+  for (FreeMemBlock &FreeMB : MemGroup.FreeMem) {
+    FreeMB.Free = trimBlockToPageSize(FreeMB.Free);
+    // We cleared the PendingMem list, so all these pointers are now invalid
+    FreeMB.PendingPrefixIndex = (unsigned)-1;
+  }
+
+  // Remove all blocks which are now empty
+  MemGroup.FreeMem.erase(
+      std::remove_if(MemGroup.FreeMem.begin(), MemGroup.FreeMem.end(),
+                     [](FreeMemBlock &FreeMB) { return FreeMB.Free.size() == 0; }),
+      MemGroup.FreeMem.end());
+
   return std::error_code();
 }
 
 void SectionMemoryManager::invalidateInstructionCache() {
   for (sys::MemoryBlock &Block : CodeMem.PendingMem)
     sys::Memory::InvalidateInstructionCache(Block.base(), Block.size());
 }
 
 SectionMemoryManager::~SectionMemoryManager() {
   for (MemoryGroup *Group : {&CodeMem, &RWDataMem, &RODataMem}) {
     for (sys::MemoryBlock &Block : Group->AllocatedMem)
       sys::Memory::releaseMappedMemory(Block);
-    for (sys::MemoryBlock &Block : Group->PendingMem)
-      sys::Memory::releaseMappedMemory(Block);
   }
 }
 
 } // namespace llvm
-

llvm/trunk/lib/Support/Unix/Memory.inc

Memory::releaseMappedMemory(MemoryBlock &M) {
   M.Address = nullptr;
   M.Size = 0;
 
   return std::error_code();
 }
 
 std::error_code
 Memory::protectMappedMemory(const MemoryBlock &M, unsigned Flags) {
+  static const size_t PageSize = Process::getPageSize();
   if (M.Address == nullptr || M.Size == 0)
     return std::error_code();
 
   if (!Flags)
     return std::error_code(EINVAL, std::generic_category());
 
   int Protect = getPosixProtectionFlags(Flags);
 
-  int Result = ::mprotect(M.Address, M.Size, Protect);
+  int Result = ::mprotect((void*)((uintptr_t)M.Address & ~(PageSize-1)), PageSize*((M.Size+PageSize-1)/PageSize), Protect);
   if (Result != 0)
     return std::error_code(errno, std::generic_category());
 
   if (Flags & MF_EXEC)
     Memory::InvalidateInstructionCache(M.Address, M.Size);
 
   return std::error_code();
 }
 
 /// AllocateRWX - Allocate a slab of memory with read/write/execute
 /// permissions.  This is typically used for JIT applications where we want
 /// to emit code to the memory then jump to it.  Getting this type of memory
 /// is very OS specific.
 ///
 MemoryBlock
 Memory::AllocateRWX(size_t NumBytes, const MemoryBlock* NearBlock,
                     std::string *ErrMsg) {
   if (NumBytes == 0) return MemoryBlock();
 
-  size_t PageSize = Process::getPageSize();
+  static const size_t PageSize = Process::getPageSize();
   size_t NumPages = (NumBytes+PageSize-1)/PageSize;
 
   int fd = -1;
 #ifdef NEED_DEV_ZERO_FOR_MMAP
   static int zero_fd = open("/dev/zero", O_RDWR);
   if (zero_fd == -1) {
     MakeErrMsg(ErrMsg, "Can't open /dev/zero device");
     return MemoryBlock();