19f617d64c5f3f2a0949f359f63b1cb3bff4b3a9bChris Lattner//===--- Allocator.cpp - Simple memory allocation abstraction -------------===// 29f617d64c5f3f2a0949f359f63b1cb3bff4b3a9bChris Lattner// 39f617d64c5f3f2a0949f359f63b1cb3bff4b3a9bChris Lattner// The LLVM Compiler Infrastructure 49f617d64c5f3f2a0949f359f63b1cb3bff4b3a9bChris Lattner// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 79f617d64c5f3f2a0949f359f63b1cb3bff4b3a9bChris Lattner// 89f617d64c5f3f2a0949f359f63b1cb3bff4b3a9bChris Lattner//===----------------------------------------------------------------------===// 99f617d64c5f3f2a0949f359f63b1cb3bff4b3a9bChris Lattner// 109f617d64c5f3f2a0949f359f63b1cb3bff4b3a9bChris Lattner// This file implements the BumpPtrAllocator interface. 119f617d64c5f3f2a0949f359f63b1cb3bff4b3a9bChris Lattner// 129f617d64c5f3f2a0949f359f63b1cb3bff4b3a9bChris Lattner//===----------------------------------------------------------------------===// 139f617d64c5f3f2a0949f359f63b1cb3bff4b3a9bChris Lattner 149f617d64c5f3f2a0949f359f63b1cb3bff4b3a9bChris Lattner#include "llvm/Support/Allocator.h" 15ea2d8780e9c78628fe5e3312ca4c17c054156c83Evgeniy Stepanov#include "llvm/Support/Compiler.h" 161f6efa3996dd1929fbc129203ce5009b620e6969Michael J. Spencer#include "llvm/Support/DataTypes.h" 17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/Memory.h" 188f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner#include "llvm/Support/Recycler.h" 197da9559c523584ce704d3e6321e613e3c2f00b3dDaniel Dunbar#include "llvm/Support/raw_ostream.h" 208f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner#include <cstring> 219f617d64c5f3f2a0949f359f63b1cb3bff4b3a9bChris Lattner 228f51a62b41a425f7fe262ff20cee835129ecc072Reid Klecknernamespace llvm { 2395eb3ad353460c6987a9d1e03a3e3e12c75b4059Reid Kleckner 248f51a62b41a425f7fe262ff20cee835129ecc072Reid KlecknerBumpPtrAllocator::BumpPtrAllocator(size_t size, size_t threshold, 258f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner SlabAllocator &allocator) 2697e910ecff5ed8b653a07fb1d014dab772931c0bBenjamin Kramer : SlabSize(size), SizeThreshold(std::min(size, threshold)), 2797e910ecff5ed8b653a07fb1d014dab772931c0bBenjamin Kramer Allocator(allocator), CurSlab(0), BytesAllocated(0) { } 2895eb3ad353460c6987a9d1e03a3e3e12c75b4059Reid Kleckner 298f51a62b41a425f7fe262ff20cee835129ecc072Reid KlecknerBumpPtrAllocator::~BumpPtrAllocator() { 308f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner DeallocateSlabs(CurSlab); 3195eb3ad353460c6987a9d1e03a3e3e12c75b4059Reid Kleckner} 3295eb3ad353460c6987a9d1e03a3e3e12c75b4059Reid Kleckner 338f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner/// AlignPtr - Align Ptr to Alignment bytes, rounding up. Alignment should 348f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner/// be a power of two. This method rounds up, so AlignPtr(7, 4) == 8 and 358f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner/// AlignPtr(8, 4) == 8. 368f51a62b41a425f7fe262ff20cee835129ecc072Reid Klecknerchar *BumpPtrAllocator::AlignPtr(char *Ptr, size_t Alignment) { 378f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner assert(Alignment && (Alignment & (Alignment - 1)) == 0 && 388f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner "Alignment is not a power of two!"); 3995eb3ad353460c6987a9d1e03a3e3e12c75b4059Reid Kleckner 408f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner // Do the alignment. 418f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner return (char*)(((uintptr_t)Ptr + Alignment - 1) & 428f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner ~(uintptr_t)(Alignment - 1)); 434bf370698a456bcc96d26184785eb4f5fab396f2Reid Kleckner} 4495eb3ad353460c6987a9d1e03a3e3e12c75b4059Reid Kleckner 458f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner/// StartNewSlab - Allocate a new slab and move the bump pointers over into 468f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner/// the new slab. Modifies CurPtr and End. 478f51a62b41a425f7fe262ff20cee835129ecc072Reid Klecknervoid BumpPtrAllocator::StartNewSlab() { 4882d96cccbc40f53c28dd8288b475e535ef017c3aBenjamin Kramer // If we allocated a big number of slabs already it's likely that we're going 4982d96cccbc40f53c28dd8288b475e535ef017c3aBenjamin Kramer // to allocate more. Increase slab size to reduce mallocs and possibly memory 5082d96cccbc40f53c28dd8288b475e535ef017c3aBenjamin Kramer // overhead. The factors are chosen conservatively to avoid overallocation. 5182d96cccbc40f53c28dd8288b475e535ef017c3aBenjamin Kramer if (BytesAllocated >= SlabSize * 128) 5282d96cccbc40f53c28dd8288b475e535ef017c3aBenjamin Kramer SlabSize *= 2; 5382d96cccbc40f53c28dd8288b475e535ef017c3aBenjamin Kramer 548f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner MemSlab *NewSlab = Allocator.Allocate(SlabSize); 558f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner NewSlab->NextPtr = CurSlab; 568f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner CurSlab = NewSlab; 578f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner CurPtr = (char*)(CurSlab + 1); 588f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner End = ((char*)CurSlab) + CurSlab->Size; 598f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner} 608f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 618f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner/// DeallocateSlabs - Deallocate all memory slabs after and including this 628f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner/// one. 638f51a62b41a425f7fe262ff20cee835129ecc072Reid Klecknervoid BumpPtrAllocator::DeallocateSlabs(MemSlab *Slab) { 648f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner while (Slab) { 658f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner MemSlab *NextSlab = Slab->NextPtr; 668f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner#ifndef NDEBUG 678f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner // Poison the memory so stale pointers crash sooner. Note we must 688f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner // preserve the Size and NextPtr fields at the beginning. 69c48edbb2fd4b7196b8bc67e7e450553602b5a754Evan Cheng sys::Memory::setRangeWritable(Slab + 1, Slab->Size - sizeof(MemSlab)); 708f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner memset(Slab + 1, 0xCD, Slab->Size - sizeof(MemSlab)); 718f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner#endif 728f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner Allocator.Deallocate(Slab); 738f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner Slab = NextSlab; 748f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner } 754bf370698a456bcc96d26184785eb4f5fab396f2Reid Kleckner} 7695eb3ad353460c6987a9d1e03a3e3e12c75b4059Reid Kleckner 778f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner/// Reset - Deallocate all but the current slab and reset the current pointer 788f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner/// to the beginning of it, freeing all memory allocated so far. 794bf370698a456bcc96d26184785eb4f5fab396f2Reid Klecknervoid BumpPtrAllocator::Reset() { 80b0322e6ddfb7f56cb7e8a770ec307fdb00cd5437Benjamin Kramer if (!CurSlab) 81b0322e6ddfb7f56cb7e8a770ec307fdb00cd5437Benjamin Kramer return; 828f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner DeallocateSlabs(CurSlab->NextPtr); 838f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner CurSlab->NextPtr = 0; 848f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner CurPtr = (char*)(CurSlab + 1); 858f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner End = ((char*)CurSlab) + CurSlab->Size; 86063d49f767e971f5cc77205d7ee8f8be36d9b013Pedro Artigas BytesAllocated = 0; 8795eb3ad353460c6987a9d1e03a3e3e12c75b4059Reid Kleckner} 8895eb3ad353460c6987a9d1e03a3e3e12c75b4059Reid Kleckner 898f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner/// Allocate - Allocate space at the specified alignment. 908f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner/// 918f51a62b41a425f7fe262ff20cee835129ecc072Reid Klecknervoid *BumpPtrAllocator::Allocate(size_t Size, size_t Alignment) { 925e6a705985f960b8d8a6df969930a51b5136bdfaBenjamin Kramer if (!CurSlab) // Start a new slab if we haven't allocated one already. 935e6a705985f960b8d8a6df969930a51b5136bdfaBenjamin Kramer StartNewSlab(); 945e6a705985f960b8d8a6df969930a51b5136bdfaBenjamin Kramer 958f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner // Keep track of how many bytes we've allocated. 968f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner BytesAllocated += Size; 978f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 9897e910ecff5ed8b653a07fb1d014dab772931c0bBenjamin Kramer // 0-byte alignment means 1-byte alignment. 9997e910ecff5ed8b653a07fb1d014dab772931c0bBenjamin Kramer if (Alignment == 0) Alignment = 1; 10097e910ecff5ed8b653a07fb1d014dab772931c0bBenjamin Kramer 1018f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner // Allocate the aligned space, going forwards from CurPtr. 1028f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner char *Ptr = AlignPtr(CurPtr, Alignment); 1038f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 1048f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner // Check if we can hold it. 1058f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner if (Ptr + Size <= End) { 1068f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner CurPtr = Ptr + Size; 107ea2d8780e9c78628fe5e3312ca4c17c054156c83Evgeniy Stepanov // Update the allocation point of this memory block in MemorySanitizer. 1089c02a276049cbd1d1511a88ebc7a22bb33658237Evgeniy Stepanov // Without this, MemorySanitizer messages for values originated from here 1099c02a276049cbd1d1511a88ebc7a22bb33658237Evgeniy Stepanov // will point to the allocation of the entire slab. 110ea2d8780e9c78628fe5e3312ca4c17c054156c83Evgeniy Stepanov __msan_allocated_memory(Ptr, Size); 1118f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner return Ptr; 1128f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner } 1138f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 1148f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner // If Size is really big, allocate a separate slab for it. 11597e910ecff5ed8b653a07fb1d014dab772931c0bBenjamin Kramer size_t PaddedSize = Size + sizeof(MemSlab) + Alignment - 1; 1167d509134dcec17f6094032196b21af5c67943f0fReid Kleckner if (PaddedSize > SizeThreshold) { 1178f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner MemSlab *NewSlab = Allocator.Allocate(PaddedSize); 1188f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 1198f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner // Put the new slab after the current slab, since we are not allocating 1208f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner // into it. 1218f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner NewSlab->NextPtr = CurSlab->NextPtr; 1228f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner CurSlab->NextPtr = NewSlab; 1238f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 1248f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner Ptr = AlignPtr((char*)(NewSlab + 1), Alignment); 1258f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner assert((uintptr_t)Ptr + Size <= (uintptr_t)NewSlab + NewSlab->Size); 126ea2d8780e9c78628fe5e3312ca4c17c054156c83Evgeniy Stepanov __msan_allocated_memory(Ptr, Size); 1278f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner return Ptr; 1288f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner } 1298f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 1308f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner // Otherwise, start a new slab and try again. 1318f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner StartNewSlab(); 1328f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner Ptr = AlignPtr(CurPtr, Alignment); 1338f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner CurPtr = Ptr + Size; 1348f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner assert(CurPtr <= End && "Unable to allocate memory!"); 135ea2d8780e9c78628fe5e3312ca4c17c054156c83Evgeniy Stepanov __msan_allocated_memory(Ptr, Size); 1364bf370698a456bcc96d26184785eb4f5fab396f2Reid Kleckner return Ptr; 13795eb3ad353460c6987a9d1e03a3e3e12c75b4059Reid Kleckner} 13895eb3ad353460c6987a9d1e03a3e3e12c75b4059Reid Kleckner 1398f51a62b41a425f7fe262ff20cee835129ecc072Reid Klecknerunsigned BumpPtrAllocator::GetNumSlabs() const { 1408f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner unsigned NumSlabs = 0; 1418f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner for (MemSlab *Slab = CurSlab; Slab != 0; Slab = Slab->NextPtr) { 1428f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner ++NumSlabs; 1438f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner } 1448f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner return NumSlabs; 1458f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner} 1468f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 1471da29dd3f85f5e3f50365d8e75efb8cbfba84381Ted Kremeneksize_t BumpPtrAllocator::getTotalMemory() const { 1481da29dd3f85f5e3f50365d8e75efb8cbfba84381Ted Kremenek size_t TotalMemory = 0; 1491da29dd3f85f5e3f50365d8e75efb8cbfba84381Ted Kremenek for (MemSlab *Slab = CurSlab; Slab != 0; Slab = Slab->NextPtr) { 1501da29dd3f85f5e3f50365d8e75efb8cbfba84381Ted Kremenek TotalMemory += Slab->Size; 1511da29dd3f85f5e3f50365d8e75efb8cbfba84381Ted Kremenek } 1521da29dd3f85f5e3f50365d8e75efb8cbfba84381Ted Kremenek return TotalMemory; 1531da29dd3f85f5e3f50365d8e75efb8cbfba84381Ted Kremenek} 1541da29dd3f85f5e3f50365d8e75efb8cbfba84381Ted Kremenek 1554bf370698a456bcc96d26184785eb4f5fab396f2Reid Klecknervoid BumpPtrAllocator::PrintStats() const { 1568f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner unsigned NumSlabs = 0; 1578f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner size_t TotalMemory = 0; 1588f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner for (MemSlab *Slab = CurSlab; Slab != 0; Slab = Slab->NextPtr) { 1598f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner TotalMemory += Slab->Size; 1608f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner ++NumSlabs; 1618f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner } 1628f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 1637da9559c523584ce704d3e6321e613e3c2f00b3dDaniel Dunbar errs() << "\nNumber of memory regions: " << NumSlabs << '\n' 1647da9559c523584ce704d3e6321e613e3c2f00b3dDaniel Dunbar << "Bytes used: " << BytesAllocated << '\n' 1657da9559c523584ce704d3e6321e613e3c2f00b3dDaniel Dunbar << "Bytes allocated: " << TotalMemory << '\n' 1667da9559c523584ce704d3e6321e613e3c2f00b3dDaniel Dunbar << "Bytes wasted: " << (TotalMemory - BytesAllocated) 1677da9559c523584ce704d3e6321e613e3c2f00b3dDaniel Dunbar << " (includes alignment, etc)\n"; 1688f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner} 1698f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 170c5b7b196770f8c3c83e4ec06c0f2a1f53b623b6fBill WendlingMallocSlabAllocator BumpPtrAllocator::DefaultSlabAllocator = 171c5b7b196770f8c3c83e4ec06c0f2a1f53b623b6fBill Wendling MallocSlabAllocator(); 1728f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 1738f51a62b41a425f7fe262ff20cee835129ecc072Reid KlecknerSlabAllocator::~SlabAllocator() { } 1748f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 1758f51a62b41a425f7fe262ff20cee835129ecc072Reid KlecknerMallocSlabAllocator::~MallocSlabAllocator() { } 1768f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 1778f51a62b41a425f7fe262ff20cee835129ecc072Reid KlecknerMemSlab *MallocSlabAllocator::Allocate(size_t Size) { 1788f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner MemSlab *Slab = (MemSlab*)Allocator.Allocate(Size, 0); 1798f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner Slab->Size = Size; 1808f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner Slab->NextPtr = 0; 1818f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner return Slab; 1828f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner} 1838f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 1848f51a62b41a425f7fe262ff20cee835129ecc072Reid Klecknervoid MallocSlabAllocator::Deallocate(MemSlab *Slab) { 1858f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner Allocator.Deallocate(Slab); 1868f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner} 1878f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner 1888f51a62b41a425f7fe262ff20cee835129ecc072Reid Klecknervoid PrintRecyclerStats(size_t Size, 1898f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner size_t Align, 1908f51a62b41a425f7fe262ff20cee835129ecc072Reid Kleckner size_t FreeListSize) { 1917da9559c523584ce704d3e6321e613e3c2f00b3dDaniel Dunbar errs() << "Recycler element size: " << Size << '\n' 1927da9559c523584ce704d3e6321e613e3c2f00b3dDaniel Dunbar << "Recycler element alignment: " << Align << '\n' 1937da9559c523584ce704d3e6321e613e3c2f00b3dDaniel Dunbar << "Number of elements free for recycling: " << FreeListSize << '\n'; 1949f617d64c5f3f2a0949f359f63b1cb3bff4b3a9bChris Lattner} 195e14d81deeb6bb3404ffee5e59ecb88304f112f4aDan Gohman 196e14d81deeb6bb3404ffee5e59ecb88304f112f4aDan Gohman} 197