BumpPtrAllocator: do the size check without moving any pointers
authorHans Wennborg <hans@hanshq.net>
Sun, 7 Sep 2014 04:24:31 +0000 (04:24 +0000)
committerHans Wennborg <hans@hanshq.net>
Sun, 7 Sep 2014 04:24:31 +0000 (04:24 +0000)
Instead of aligning and moving the CurPtr forward, and then comparing
with End, simply calculate how much space is needed, and compare that
to how much is available.

Hopefully this avoids any doubts about comparing addresses possibly
derived from past the end of the slab array, overflowing, etc.

Also add a test where aligning CurPtr would move it past End.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@217330 91177308-0d34-0410-b5e6-96231b3b80d8

include/llvm/Support/Allocator.h
include/llvm/Support/MathExtras.h
unittests/Support/AllocatorTest.cpp

index 05dccec..ff08622 100644 (file)
@@ -209,12 +209,12 @@ public:
     // Keep track of how many bytes we've allocated.
     BytesAllocated += Size;
 
     // Keep track of how many bytes we've allocated.
     BytesAllocated += Size;
 
-    // Allocate the aligned space, going forwards from CurPtr.
-    uintptr_t AlignedAddr = alignAddr(CurPtr, Alignment);
+    size_t Adjustment = alignmentAdjustment(CurPtr, Alignment);
+    assert(Adjustment + Size >= Size && "Adjustment + Size must not overflow");
 
 
-    // Check if we can hold it.
-    if (AlignedAddr + Size <= (uintptr_t)End) {
-      char *AlignedPtr = (char*)AlignedAddr;
+    // Check if we have enough space.
+    if (Adjustment + Size <= size_t(End - CurPtr)) {
+      char *AlignedPtr = CurPtr + Adjustment;
       CurPtr = AlignedPtr + Size;
       // Update the allocation point of this memory block in MemorySanitizer.
       // Without this, MemorySanitizer messages for values originated from here
       CurPtr = AlignedPtr + Size;
       // Update the allocation point of this memory block in MemorySanitizer.
       // Without this, MemorySanitizer messages for values originated from here
@@ -238,7 +238,7 @@ public:
 
     // Otherwise, start a new slab and try again.
     StartNewSlab();
 
     // Otherwise, start a new slab and try again.
     StartNewSlab();
-    AlignedAddr = alignAddr(CurPtr, Alignment);
+    uintptr_t AlignedAddr = alignAddr(CurPtr, Alignment);
     assert(AlignedAddr + Size <= (uintptr_t)End &&
            "Unable to allocate memory!");
     char *AlignedPtr = (char*)AlignedAddr;
     assert(AlignedAddr + Size <= (uintptr_t)End &&
            "Unable to allocate memory!");
     char *AlignedPtr = (char*)AlignedAddr;
index adfca78..6a104e7 100644 (file)
@@ -558,9 +558,17 @@ inline uintptr_t alignAddr(void *Addr, size_t Alignment) {
   assert(Alignment && isPowerOf2_64((uint64_t)Alignment) &&
          "Alignment is not a power of two!");
 
   assert(Alignment && isPowerOf2_64((uint64_t)Alignment) &&
          "Alignment is not a power of two!");
 
+  assert((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr);
+
   return (((uintptr_t)Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1));
 }
 
   return (((uintptr_t)Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1));
 }
 
+/// \brief Returns the necessary adjustment for aligning \c Ptr to \c Alignment
+/// bytes, rounding up.
+inline size_t alignmentAdjustment(void *Ptr, size_t Alignment) {
+  return alignAddr(Ptr, Alignment) - (uintptr_t)Ptr;
+}
+
 /// NextPowerOf2 - Returns the next power of two (in 64-bits)
 /// that is strictly greater than A.  Returns zero on overflow.
 inline uint64_t NextPowerOf2(uint64_t A) {
 /// NextPowerOf2 - Returns the next power of two (in 64-bits)
 /// that is strictly greater than A.  Returns zero on overflow.
 inline uint64_t NextPowerOf2(uint64_t A) {
index 7789df5..616f8af 100644 (file)
@@ -115,6 +115,18 @@ TEST(AllocatorTest, TestSmallSlabSize) {
   EXPECT_EQ(1U, Alloc.GetNumSlabs());
 }
 
   EXPECT_EQ(1U, Alloc.GetNumSlabs());
 }
 
+// Test requesting alignment that goes past the end of the current slab.
+TEST(AllocatorTest, TestAlignmentPastSlab) {
+  BumpPtrAllocator Alloc;
+  Alloc.Allocate(1234, 1);
+
+  // Any attempt to align the pointer in the current slab would move it beyond
+  // the end of that slab.
+  Alloc.Allocate(1024, 8192);
+
+  EXPECT_EQ(2U, Alloc.GetNumSlabs());
+}
+
 // Mock slab allocator that returns slabs aligned on 4096 bytes.  There is no
 // easy portable way to do this, so this is kind of a hack.
 class MockSlabAllocator {
 // Mock slab allocator that returns slabs aligned on 4096 bytes.  There is no
 // easy portable way to do this, so this is kind of a hack.
 class MockSlabAllocator {