Changes in directory llvm-poolalloc/runtime/BoundsCheckAllocator:
PoolAllocator.cpp added (r1.1) --- Log message: *** empty log message *** --- Diffs of the changes: (+1093 -0) PoolAllocator.cpp | 1093 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 1093 insertions(+) Index: llvm-poolalloc/runtime/BoundsCheckAllocator/PoolAllocator.cpp diff -c /dev/null llvm-poolalloc/runtime/BoundsCheckAllocator/PoolAllocator.cpp:1.1 *** /dev/null Thu Dec 22 10:49:02 2005 --- llvm-poolalloc/runtime/BoundsCheckAllocator/PoolAllocator.cpp Thu Dec 22 10:48:52 2005 *************** *** 0 **** --- 1,1093 ---- + //===- PoolAllocator.cpp - Simple free-list based pool allocator ----------===// + // + // The LLVM Compiler Infrastructure + // + // This file was developed by the LLVM research group and is distributed under + // the University of Illinois Open Source License. See LICENSE.TXT for details. + // + //===----------------------------------------------------------------------===// + // + // This file is one possible implementation of the LLVM pool allocator runtime + // library. + // + // FIXME: + // The pointer compression functions are not thread safe. + //===----------------------------------------------------------------------===// + + #include "PoolAllocator.h" + #include "poolalloc/MMAPSupport.h" + #include <stdlib.h> + #include <stdio.h> + #include <string.h> + + typedef long intptr_t; + typedef unsigned long uintptr_t; + + // Performance tweaking macros. + #define INITIAL_SLAB_SIZE 4096 + #define LARGE_SLAB_SIZE 4096 + + #ifndef NDEBUG + // Configuration macros. Define up to one of these. + #define PRINT_NUM_POOLS // Print use dynamic # pools info + //#define PRINT_POOLDESTROY_STATS // When pools are destroyed, print stats + //#define PRINT_POOL_TRACE // Print a full trace + #define ENABLE_POOL_IDS // PID for access/pool traces + + + // ALWAYS_USE_MALLOC_FREE - Make poolalloc/free always call malloc/free. Note + // that if the poolfree optimization is in use that this will cause memory + // leaks! + //#define ALWAYS_USE_MALLOC_FREE + #endif + + //===----------------------------------------------------------------------===// + // Pool Debugging stuff. + //===----------------------------------------------------------------------===// + + #if defined(ALWAYS_USE_MALLOC_FREE) + #define DO_IF_FORCE_MALLOCFREE(x) x + #else + #define DO_IF_FORCE_MALLOCFREE(x) + #endif + + + #if !defined(PRINT_POOL_TRACE) + #define DO_IF_TRACE(X) + #else + #define ENABLE_POOL_IDS + #define DO_IF_TRACE(X) X + #define PRINT_POOLDESTROY_STATS + #endif + + #if defined(ENABLE_POOL_IDS) + struct PoolID { + void *PD; + unsigned ID; + }; + + struct PoolID *PoolIDs = 0; + static unsigned NumLivePools = 0; + static unsigned NumPoolIDsAllocated = 0; + static unsigned CurPoolID = 0; + + static unsigned addPoolNumber(void *PD) { + if (NumLivePools == NumPoolIDsAllocated) { + NumPoolIDsAllocated = (10+NumPoolIDsAllocated)*2; + PoolIDs = (PoolID*)realloc(PoolIDs, sizeof(PoolID)*NumPoolIDsAllocated); + } + + PoolIDs[NumLivePools].PD = PD; + PoolIDs[NumLivePools].ID = ++CurPoolID; + NumLivePools++; + return CurPoolID; + } + + static unsigned getPoolNumber(void *PD) { + if (PD == 0) return ~0; + for (unsigned i = 0; i != NumLivePools; ++i) + if (PoolIDs[i].PD == PD) + return PoolIDs[i].ID; + fprintf(stderr, "INVALID/UNKNOWN POOL DESCRIPTOR: 0x%lX\n",(unsigned long)PD); + return 0; + } + + static unsigned removePoolNumber(void *PD) { + for (unsigned i = 0; i != NumLivePools; ++i) + if (PoolIDs[i].PD == PD) { + unsigned PN = PoolIDs[i].ID; + memmove(&PoolIDs[i], &PoolIDs[i+1], sizeof(PoolID)*(NumLivePools-i-1)); + --NumLivePools; + return PN; + } + fprintf(stderr, "INVALID/UNKNOWN POOL DESCRIPTOR: 0x%lX\n",(unsigned long)PD); + return 0; + } + + static void PrintPoolStats(void *Pool); + template<typename PoolTraits> + static void PrintLivePoolInfo() { + for (unsigned i = 0; i != NumLivePools; ++i) { + fprintf(stderr, "[%d] pool at exit ", PoolIDs[i].ID); + PrintPoolStats((PoolTy<PoolTraits>*)PoolIDs[i].PD); + } + } + #endif + + #ifdef PRINT_POOLDESTROY_STATS + #define DO_IF_POOLDESTROY_STATS(X) X + #define PRINT_NUM_POOLS + + template<typename PoolTraits> + static void PrintPoolStats(PoolTy<PoolTraits> *Pool) { + fprintf(stderr, + "(0x%X) BytesAlloc=%d NumObjs=%d" + " AvgObjSize=%d NextAllocSize=%d DeclaredSize=%d\n", + Pool, Pool->BytesAllocated, Pool->NumObjects, + Pool->NumObjects ? Pool->BytesAllocated/Pool->NumObjects : 0, + Pool->AllocSize, Pool->DeclaredSize); + } + + #else + #define DO_IF_POOLDESTROY_STATS(X) + #endif + + #ifdef PRINT_NUM_POOLS + static unsigned PoolCounter = 0; + static unsigned PoolsInited = 0; + + // MaxHeapSize - The maximum size of the heap ever. + static unsigned MaxHeapSize = 0; + + // CurHeapSize - The current size of the heap. + static unsigned CurHeapSize = 0; + + template<typename PoolTraits> + static void PoolCountPrinter() { + DO_IF_TRACE(PrintLivePoolInfo<PoolTraits>()); + fprintf(stderr, "\n\n" + "*** %d DYNAMIC POOLS INITIALIZED ***\n\n" + "*** %d DYNAMIC POOLS ALLOCATED FROM ***\n\n", + PoolsInited, PoolCounter); + fprintf(stderr, "MaxHeapSize = %fKB HeapSizeAtExit = %fKB " + "NOTE: only valid if using Heuristic=AllPools and no " + "bumpptr/realloc!\n", MaxHeapSize/1024.0, CurHeapSize/1024.0); + } + + template<typename PoolTraits> + static void InitPrintNumPools() { + static bool Initialized = 0; + if (!Initialized) { + Initialized = 1; + atexit(PoolCountPrinter<PoolTraits>); + } + } + + #define DO_IF_PNP(X) X + #else + #define DO_IF_PNP(X) + #endif + + //===----------------------------------------------------------------------===// + // PoolSlab implementation + //===----------------------------------------------------------------------===// + + + template<typename PoolTraits> + static void AddNodeToFreeList(PoolTy<PoolTraits> *Pool, + FreedNodeHeader<PoolTraits> *FreeNode) { + typename PoolTraits::FreeNodeHeaderPtrTy *FreeList; + if (FreeNode->Header.Size == Pool->DeclaredSize) + FreeList = &Pool->ObjFreeList; + else + FreeList = &Pool->OtherFreeList; + + void *PoolBase = Pool->Slabs; + + typename PoolTraits::FreeNodeHeaderPtrTy FreeNodeIdx = + PoolTraits::FNHPtrToIndex(FreeNode, PoolBase); + + FreeNode->Prev = 0; // First on the list. + FreeNode->Next = *FreeList; + *FreeList = FreeNodeIdx; + if (FreeNode->Next) + PoolTraits::IndexToFNHPtr(FreeNode->Next, PoolBase)->Prev = FreeNodeIdx; + } + + template<typename PoolTraits> + static void UnlinkFreeNode(PoolTy<PoolTraits> *Pool, + FreedNodeHeader<PoolTraits> *FNH) { + void *PoolBase = Pool->Slabs; + + // Make the predecessor point to our next node. + if (FNH->Prev) + PoolTraits::IndexToFNHPtr(FNH->Prev, PoolBase)->Next = FNH->Next; + else { + typename PoolTraits::FreeNodeHeaderPtrTy NodeIdx = + PoolTraits::FNHPtrToIndex(FNH, PoolBase); + + if (Pool->ObjFreeList == NodeIdx) + Pool->ObjFreeList = FNH->Next; + else { + assert(Pool->OtherFreeList == NodeIdx && + "Prev Ptr is null but not at head of free list?"); + Pool->OtherFreeList = FNH->Next; + } + } + + if (FNH->Next) + PoolTraits::IndexToFNHPtr(FNH->Next, PoolBase)->Prev = FNH->Prev; + } + + + // PoolSlab Structure - Hold multiple objects of the current node type. + // Invariants: FirstUnused <= UsedEnd + // + template<typename PoolTraits> + struct PoolSlab { + // Next - This link is used when we need to traverse the list of slabs in a + // pool, for example, to destroy them all. + PoolSlab<PoolTraits> *Next; + + public: + static void create(PoolTy<PoolTraits> *Pool, unsigned SizeHint); + static void *create_for_bp(PoolTy<PoolTraits> *Pool); + static void create_for_ptrcomp(PoolTy<PoolTraits> *Pool, + void *Mem, unsigned Size); + void destroy(); + + PoolSlab<PoolTraits> *getNext() const { return Next; } + }; + + // create - Create a new (empty) slab and add it to the end of the Pools list. + template<typename PoolTraits> + void PoolSlab<PoolTraits>::create(PoolTy<PoolTraits> *Pool, unsigned SizeHint) { + if (Pool->DeclaredSize == 0) { + unsigned Align = Pool->Alignment; + if (SizeHint < sizeof(FreedNodeHeader<PoolTraits>) - + sizeof(NodeHeader<PoolTraits>)) + SizeHint = sizeof(FreedNodeHeader<PoolTraits>) - + sizeof(NodeHeader<PoolTraits>); + SizeHint = SizeHint+sizeof(FreedNodeHeader<PoolTraits>)+(Align-1); + SizeHint = (SizeHint & ~(Align-1))-sizeof(FreedNodeHeader<PoolTraits>); + // Pool->DeclaredSize = SizeHint; + } + + unsigned Size = Pool->AllocSize; + Pool->AllocSize <<= 1; + Size = (Size+SizeHint-1) / SizeHint * SizeHint; + PoolSlab *PS = (PoolSlab*)malloc(Size+sizeof(PoolSlab<PoolTraits>) + + sizeof(NodeHeader<PoolTraits>) + + sizeof(FreedNodeHeader<PoolTraits>)); + char *PoolBody = (char*)(PS+1); + + // If the Alignment is greater than the size of the FreedNodeHeader, skip over + // some space so that the a "free pointer + sizeof(FreedNodeHeader)" is always + // aligned. + unsigned Alignment = Pool->Alignment; + if (Alignment > sizeof(FreedNodeHeader<PoolTraits>)) { + PoolBody += Alignment-sizeof(FreedNodeHeader<PoolTraits>); + Size -= Alignment-sizeof(FreedNodeHeader<PoolTraits>); + } + + // Add the body of the slab to the free list. + FreedNodeHeader<PoolTraits> *SlabBody =(FreedNodeHeader<PoolTraits>*)PoolBody; + SlabBody->Header.Size = Size; + AddNodeToFreeList(Pool, SlabBody); + + // Make sure to add a marker at the end of the slab to prevent the coallescer + // from trying to merge off the end of the page. + FreedNodeHeader<PoolTraits> *End = + (FreedNodeHeader<PoolTraits>*)(PoolBody + sizeof(NodeHeader<PoolTraits>)+ + Size); + End->Header.Size = ~0; // Looks like an allocated chunk + + // Add the slab to the list... + PS->Next = Pool->Slabs; + Pool->Slabs = PS; + } + + /// create_for_bp - This creates a slab for a bump-pointer pool. + template<typename PoolTraits> + void *PoolSlab<PoolTraits>::create_for_bp(PoolTy<PoolTraits> *Pool) { + unsigned Size = Pool->AllocSize; + Pool->AllocSize <<= 1; + PoolSlab *PS = (PoolSlab*)malloc(Size+sizeof(PoolSlab)); + char *PoolBody = (char*)(PS+1); + if (sizeof(PoolSlab) == 4) + PoolBody += 4; // No reason to start out unaligned. + + // Update the end pointer. + Pool->OtherFreeList = (FreedNodeHeader<PoolTraits>*)((char*)(PS+1)+Size); + + // Add the slab to the list... + PS->Next = Pool->Slabs; + Pool->Slabs = PS; + return PoolBody; + } + + /// create_for_ptrcomp - Initialize a chunk of memory 'Mem' of size 'Size' for + /// pointer compression. + template<typename PoolTraits> + void PoolSlab<PoolTraits>::create_for_ptrcomp(PoolTy<PoolTraits> *Pool, + void *SMem, unsigned Size) { + if (Pool->DeclaredSize == 0) { + unsigned Align = Pool->Alignment; + unsigned SizeHint = sizeof(FreedNodeHeader<PoolTraits>) - + sizeof(NodeHeader<PoolTraits>); + SizeHint = SizeHint+sizeof(FreedNodeHeader<PoolTraits>)+(Align-1); + SizeHint = (SizeHint & ~(Align-1))-sizeof(FreedNodeHeader<PoolTraits>); + Pool->DeclaredSize = SizeHint; + } + + Size -= sizeof(PoolSlab) + sizeof(NodeHeader<PoolTraits>) + + sizeof(FreedNodeHeader<PoolTraits>); + PoolSlab *PS = (PoolSlab*)SMem; + char *PoolBody = (char*)(PS+1); + + // If the Alignment is greater than the size of the NodeHeader, skip over some + // space so that the a "free pointer + sizeof(NodeHeader)" is always aligned + // for user data. + unsigned Alignment = Pool->Alignment; + if (Alignment > sizeof(NodeHeader<PoolTraits>)) { + PoolBody += Alignment-sizeof(NodeHeader<PoolTraits>); + Size -= Alignment-sizeof(NodeHeader<PoolTraits>); + } + + // Add the body of the slab to the free list. + FreedNodeHeader<PoolTraits> *SlabBody =(FreedNodeHeader<PoolTraits>*)PoolBody; + SlabBody->Header.Size = Size; + AddNodeToFreeList(Pool, SlabBody); + + // Make sure to add a marker at the end of the slab to prevent the coallescer + // from trying to merge off the end of the page. + FreedNodeHeader<PoolTraits> *End = + (FreedNodeHeader<PoolTraits>*)(PoolBody + sizeof(NodeHeader<PoolTraits>) + + Size); + End->Header.Size = ~0; // Looks like an allocated chunk + PS->Next = 0; + } + + + template<typename PoolTraits> + void PoolSlab<PoolTraits>::destroy() { + free(this); + } + + //===----------------------------------------------------------------------===// + // + // Bump-pointer pool allocator library implementation + // + //===----------------------------------------------------------------------===// + + void poolinit_bp(PoolTy<NormalPoolTraits> *Pool, unsigned ObjAlignment) { + DO_IF_PNP(memset(Pool, 0, sizeof(PoolTy<NormalPoolTraits>))); + Pool->Slabs = 0; + if (ObjAlignment < 4) ObjAlignment = __alignof(double); + Pool->AllocSize = INITIAL_SLAB_SIZE; + Pool->Alignment = ObjAlignment; + Pool->LargeArrays = 0; + Pool->ObjFreeList = 0; // This is our bump pointer. + Pool->OtherFreeList = 0; // This is our end pointer. + + unsigned PID; + #ifdef ENABLE_POOL_IDS + PID = addPoolNumber(Pool); + #endif + + DO_IF_TRACE(fprintf(stderr, "[%d] poolinit_bp(0x%X, %d)\n", + PID, Pool, ObjAlignment)); + DO_IF_PNP(++PoolsInited); // Track # pools initialized + DO_IF_PNP(InitPrintNumPools<NormalPoolTraits>()); + } + + void *poolalloc_bp(PoolTy<NormalPoolTraits> *Pool, unsigned NumBytes) { + DO_IF_FORCE_MALLOCFREE(return malloc(NumBytes)); + assert(Pool && "Bump pointer pool does not support null PD!"); + DO_IF_TRACE(fprintf(stderr, "[%d] poolalloc_bp(%d) -> ", + getPoolNumber(Pool), NumBytes)); + DO_IF_PNP(if (Pool->NumObjects == 0) ++PoolCounter); // Track # pools. + + if (NumBytes >= LARGE_SLAB_SIZE) + goto LargeObject; + + DO_IF_PNP(++Pool->NumObjects); + DO_IF_PNP(Pool->BytesAllocated += NumBytes); + + if (NumBytes < 1) NumBytes = 1; + + uintptr_t Alignment; + char *BumpPtr, *EndPtr; + Alignment = Pool->Alignment-1; + BumpPtr = (char*)Pool->ObjFreeList; // Get our bump pointer. + EndPtr = (char*)Pool->OtherFreeList; // Get our end pointer. + + TryAgain: + // Align the bump pointer to the required boundary. + BumpPtr = (char*)(intptr_t((BumpPtr+Alignment)) & ~Alignment); + + if (BumpPtr + NumBytes < EndPtr) { + void *Result = BumpPtr; + // Update bump ptr. + Pool->ObjFreeList = (FreedNodeHeader<NormalPoolTraits>*)(BumpPtr+NumBytes); + DO_IF_TRACE(fprintf(stderr, "%p\n", Result)); + return Result; + } + + BumpPtr = (char*)PoolSlab<NormalPoolTraits>::create_for_bp(Pool); + EndPtr = (char*)Pool->OtherFreeList; // Get our updated end pointer. + goto TryAgain; + + LargeObject: + // Otherwise, the allocation is a large array. Since we're not going to be + // able to help much for this allocation, simply pass it on to malloc. + LargeArrayHeader *LAH = (LargeArrayHeader*)malloc(sizeof(LargeArrayHeader) + + NumBytes); + LAH->Size = NumBytes; + LAH->Marker = ~0U; + LAH->LinkIntoList(&Pool->LargeArrays); + DO_IF_TRACE(fprintf(stderr, "%p [large]\n", LAH+1)); + return LAH+1; + } + + void pooldestroy_bp(PoolTy<NormalPoolTraits> *Pool) { + assert(Pool && "Null pool pointer passed in to pooldestroy!\n"); + + unsigned PID; + #ifdef ENABLE_POOL_IDS + PID = removePoolNumber(Pool); + #endif + DO_IF_TRACE(fprintf(stderr, "[%d] pooldestroy_bp", PID)); + DO_IF_POOLDESTROY_STATS(PrintPoolStats(Pool)); + + // Free all allocated slabs. + PoolSlab<NormalPoolTraits> *PS = Pool->Slabs; + while (PS) { + PoolSlab<NormalPoolTraits> *Next = PS->getNext(); + PS->destroy(); + PS = Next; + } + + // Free all of the large arrays. + LargeArrayHeader *LAH = Pool->LargeArrays; + while (LAH) { + LargeArrayHeader *Next = LAH->Next; + free(LAH); + LAH = Next; + } + } + + + + //===----------------------------------------------------------------------===// + // + // Pool allocator library implementation + // + //===----------------------------------------------------------------------===// + + // poolinit - Initialize a pool descriptor to empty + // + template<typename PoolTraits> + static void poolinit_internal(PoolTy<PoolTraits> *Pool, + unsigned DeclaredSize, unsigned ObjAlignment) { + assert(Pool && "Null pool pointer passed into poolinit!\n"); + memset(Pool, 0, sizeof(PoolTy<PoolTraits>)); + Pool->splay = new_splay(); + Pool->AllocSize = INITIAL_SLAB_SIZE; + + if (ObjAlignment < 4) ObjAlignment = __alignof(double); + Pool->Alignment = ObjAlignment; + + // Round the declared size up to an alignment boundary-header size, just like + // we have to do for objects. + if (DeclaredSize) { + if (DeclaredSize < sizeof(FreedNodeHeader<PoolTraits>) - + sizeof(NodeHeader<PoolTraits>)) + DeclaredSize = sizeof(FreedNodeHeader<PoolTraits>) - + sizeof(NodeHeader<PoolTraits>); + DeclaredSize = DeclaredSize+sizeof(FreedNodeHeader<PoolTraits>) + + (ObjAlignment-1); + DeclaredSize = (DeclaredSize & ~(ObjAlignment-1)) - + sizeof(FreedNodeHeader<PoolTraits>); + } + + Pool->DeclaredSize = DeclaredSize; + + unsigned PID; + #ifdef ENABLE_POOL_IDS + PID = addPoolNumber(Pool); + #endif + DO_IF_TRACE(fprintf(stderr, "[%d] poolinit%s(0x%X, %d, %d)\n", + PID, PoolTraits::getSuffix(), + Pool, DeclaredSize, ObjAlignment)); + DO_IF_PNP(++PoolsInited); // Track # pools initialized + DO_IF_PNP(InitPrintNumPools<PoolTraits>()); + } + + void poolinit(PoolTy<NormalPoolTraits> *Pool, + unsigned DeclaredSize, unsigned ObjAlignment) { + poolinit_internal(Pool, DeclaredSize, ObjAlignment); + } + + // pooldestroy - Release all memory allocated for a pool + // + void pooldestroy(PoolTy<NormalPoolTraits> *Pool) { + assert(Pool && "Null pool pointer passed in to pooldestroy!\n"); + free_splay(Pool->splay); + unsigned PID; + #ifdef ENABLE_POOL_IDS + PID = removePoolNumber(Pool); + #endif + DO_IF_TRACE(fprintf(stderr, "[%d] pooldestroy", PID)); + DO_IF_POOLDESTROY_STATS(PrintPoolStats(Pool)); + + // Free all allocated slabs. + PoolSlab<NormalPoolTraits> *PS = Pool->Slabs; + while (PS) { + PoolSlab<NormalPoolTraits> *Next = PS->getNext(); + PS->destroy(); + PS = Next; + } + + // Free all of the large arrays. + LargeArrayHeader *LAH = Pool->LargeArrays; + while (LAH) { + LargeArrayHeader *Next = LAH->Next; + free(LAH); + LAH = Next; + } + } + + template<typename PoolTraits> + static void *poolalloc_internal(PoolTy<PoolTraits> *Pool, unsigned NumBytes) { + DO_IF_TRACE(fprintf(stderr, "[%d] poolalloc%s(%d) -> ", + getPoolNumber(Pool), PoolTraits::getSuffix(), NumBytes)); + + // If a null pool descriptor is passed in, this is not a pool allocated data + // structure. Hand off to the system malloc. + if (Pool == 0) { + // std::cerr << "Null descriptor is passed in "; + abort(); + void *Result = malloc(NumBytes); + DO_IF_TRACE(fprintf(stderr, "0x%X [malloc]\n", Result)); + return Result; + } + DO_IF_PNP(if (Pool->NumObjects == 0) ++PoolCounter); // Track # pools. + + // Objects must be at least 8 bytes to hold the FreedNodeHeader object when + // they are freed. This also handles allocations of 0 bytes. + if (NumBytes < (sizeof(FreedNodeHeader<PoolTraits>) - + sizeof(NodeHeader<PoolTraits>))) + NumBytes = sizeof(FreedNodeHeader<PoolTraits>) - + sizeof(NodeHeader<PoolTraits>); + + // Adjust the size so that memory allocated from the pool is always on the + // proper alignment boundary. + unsigned Alignment = Pool->Alignment; + NumBytes = NumBytes+sizeof(FreedNodeHeader<PoolTraits>) + + (Alignment-1); // Round up + NumBytes = (NumBytes & ~(Alignment-1)) - + sizeof(FreedNodeHeader<PoolTraits>); // Truncate + + DO_IF_PNP(CurHeapSize += (NumBytes + sizeof(NodeHeader<PoolTraits>))); + DO_IF_PNP(if (CurHeapSize > MaxHeapSize) MaxHeapSize = CurHeapSize); + + DO_IF_PNP(++Pool->NumObjects); + DO_IF_PNP(Pool->BytesAllocated += NumBytes); + + // Fast path - allocate objects off the object list. + if (NumBytes == Pool->DeclaredSize && Pool->ObjFreeList != 0) { + typename PoolTraits::FreeNodeHeaderPtrTy NodeIdx = Pool->ObjFreeList; + void *PoolBase = Pool->Slabs; + FreedNodeHeader<PoolTraits> *Node = + PoolTraits::IndexToFNHPtr(NodeIdx, PoolBase); + UnlinkFreeNode(Pool, Node); + assert(NumBytes == Node->Header.Size); + + Node->Header.Size = NumBytes|1; // Mark as allocated + //store it in the splay tree + if (NumBytes != Pool->DeclaredSize) + splay_insert_ptr(Pool->splay, (unsigned long)(&Node->Header+1), NumBytes); + DO_IF_TRACE(fprintf(stderr, "0x%X\n", &Node->Header+1)); + return &Node->Header+1; + } + + if (PoolTraits::UseLargeArrayObjects && + NumBytes >= LARGE_SLAB_SIZE-sizeof(PoolSlab<PoolTraits>) - + sizeof(NodeHeader<PoolTraits>)) + goto LargeObject; + + // Fast path. In the common case, we can allocate a portion of the node at + // the front of the free list. + do { + void *PoolBase = Pool->Slabs; + FreedNodeHeader<PoolTraits> *FirstNode = + PoolTraits::IndexToFNHPtr(Pool->OtherFreeList, PoolBase); + if (FirstNode) { + unsigned FirstNodeSize = FirstNode->Header.Size; + if (FirstNodeSize >= NumBytes) { + if (FirstNodeSize >= 2*NumBytes+sizeof(NodeHeader<PoolTraits>)) { + // Put the remainder back on the list... + FreedNodeHeader<PoolTraits> *NextNodes = + (FreedNodeHeader<PoolTraits>*)((char*)FirstNode + + sizeof(NodeHeader<PoolTraits>) +NumBytes); + + // Remove from list + UnlinkFreeNode(Pool, FirstNode); + + NextNodes->Header.Size = FirstNodeSize-NumBytes - + sizeof(NodeHeader<PoolTraits>); + AddNodeToFreeList(Pool, NextNodes); + + } else { + UnlinkFreeNode(Pool, FirstNode); + NumBytes = FirstNodeSize; + } + FirstNode->Header.Size = NumBytes|1; // Mark as allocated + DO_IF_TRACE(fprintf(stderr, "0x%X\n", &FirstNode->Header+1)); + //Store it in the splay tree.... + // Pool->splay = + if (NumBytes != Pool->DeclaredSize) + splay_insert_ptr(Pool->splay, (unsigned long) (&FirstNode->Header+1), NumBytes); + return &FirstNode->Header+1; + } + + // Perform a search of the free list, taking the front of the first free + // chunk that is big enough. + typename PoolTraits::FreeNodeHeaderPtrTy *FN = &Pool->OtherFreeList; + FreedNodeHeader<PoolTraits> *FNN = FirstNode; + + // Search the list for the first-fit. + while (FNN && FNN->Header.Size < NumBytes) { + // Advance FN to point to the Next field of FNN. + FN = &FNN->Next; + + // Advance FNN to point to whatever the next node points to (null or the + // next node in the free list). + FNN = PoolTraits::IndexToFNHPtr(*FN, PoolBase); + } + + if (FNN) { + // We found a slab big enough. If it's a perfect fit, just unlink + // from the free list, otherwise, slice a little bit off and adjust + // the free list. + if (FNN->Header.Size > 2*NumBytes+sizeof(NodeHeader<PoolTraits>)) { + UnlinkFreeNode(Pool, FNN); + + // Put the remainder back on the list... + FreedNodeHeader<PoolTraits> *NextNodes = + (FreedNodeHeader<PoolTraits>*)((char*)FNN + + sizeof(NodeHeader<PoolTraits>) + + NumBytes); + NextNodes->Header.Size = FNN->Header.Size-NumBytes - + sizeof(NodeHeader<PoolTraits>); + AddNodeToFreeList(Pool, NextNodes); + } else { + UnlinkFreeNode(Pool, FNN); + NumBytes = FNN->Header.Size; + } + FNN->Header.Size = NumBytes|1; // Mark as allocated + DO_IF_TRACE(fprintf(stderr, "0x%X\n", &FNN->Header+1)); + //Store it in the splay tree.... + // Pool->splay = + if (NumBytes != Pool->DeclaredSize) + splay_insert_ptr(Pool->splay, (unsigned long) (&FNN->Header+1), NumBytes); + return &FNN->Header+1; + } + } + + // If we are not allowed to grow this pool, don't. + if (!PoolTraits::CanGrowPool) { + abort(); + return 0; + } + + // Oops, we didn't find anything on the free list big enough! Allocate + // another slab and try again. + PoolSlab<PoolTraits>::create(Pool, NumBytes); + } while (1); + + LargeObject: + // Otherwise, the allocation is a large array. Since we're not going to be + // able to help much for this allocation, simply pass it on to malloc. + LargeArrayHeader *LAH = (LargeArrayHeader*)malloc(sizeof(LargeArrayHeader) + + NumBytes); + LAH->Size = NumBytes; + LAH->Marker = ~0U; + LAH->LinkIntoList(&Pool->LargeArrays); + DO_IF_TRACE(fprintf(stderr, "0x%X [large]\n", LAH+1)); + //Store it in the splay tree.... + //Pool->splay = + if (NumBytes != Pool->DeclaredSize) + splay_insert_ptr(Pool->splay, (unsigned long) (LAH+1), NumBytes); + return LAH+1; + } + + template<typename PoolTraits> + static void poolfree_internal(PoolTy<PoolTraits> *Pool, void *Node) { + if (Node == 0) return; + DO_IF_TRACE(fprintf(stderr, "[%d] poolfree%s(%p) ", + getPoolNumber(Pool), PoolTraits::getSuffix(), Node)); + + // If a null pool descriptor is passed in, this is not a pool allocated data + // structure. Hand off to the system free. + if (Pool == 0) { + abort(); + free(Node); + DO_IF_TRACE(fprintf(stderr, "[free]\n")); + return; + } + Splay *splay = splay_find_ptr(Pool->splay, (unsigned long)Node); + splay_delete_node(splay); + // Check to see how many elements were allocated to this node... + FreedNodeHeader<PoolTraits> *FNH = + (FreedNodeHeader<PoolTraits>*)((char*)Node-sizeof(NodeHeader<PoolTraits>)); + assert((FNH->Header.Size & 1) && "Node not allocated!"); + unsigned Size = FNH->Header.Size & ~1; + + if (Size == ~1U) goto LargeArrayCase; + DO_IF_TRACE(fprintf(stderr, "%d bytes\n", Size)); + + DO_IF_PNP(CurHeapSize -= (Size + sizeof(NodeHeader<PoolTraits>))); + + // If the node immediately after this one is also free, merge it into node. + FreedNodeHeader<PoolTraits> *NextFNH; + NextFNH = (FreedNodeHeader<PoolTraits>*)((char*)Node+Size); + while ((NextFNH->Header.Size & 1) == 0) { + // Unlink NextFNH from the freelist that it is in. + UnlinkFreeNode(Pool, NextFNH); + Size += sizeof(NodeHeader<PoolTraits>)+NextFNH->Header.Size; + NextFNH = (FreedNodeHeader<PoolTraits>*)((char*)Node+Size); + } + + // If there are already nodes on the freelist, see if these blocks can be + // coallesced into one of the early blocks on the front of the list. This is + // a simple check that prevents many horrible forms of fragmentation, + // particularly when freeing objects in allocation order. + // + if (Pool->ObjFreeList) { + void *PoolBase = Pool->Slabs; + FreedNodeHeader<PoolTraits> *ObjFNH = + PoolTraits::IndexToFNHPtr(Pool->ObjFreeList, PoolBase); + + if ((char*)ObjFNH + sizeof(NodeHeader<PoolTraits>) + + ObjFNH->Header.Size == (char*)FNH) { + // Merge this with a node that is already on the object size free list. + // Because the object is growing, we will never be able to find it if we + // leave it on the object freelist. + UnlinkFreeNode(Pool, ObjFNH); + ObjFNH->Header.Size += Size+sizeof(NodeHeader<PoolTraits>); + AddNodeToFreeList(Pool, ObjFNH); + return; + } + } + + if (Pool->OtherFreeList) { + void *PoolBase = Pool->Slabs; + FreedNodeHeader<PoolTraits> *OFNH = + PoolTraits::IndexToFNHPtr(Pool->OtherFreeList, PoolBase); + + if ((char*)OFNH + sizeof(NodeHeader<PoolTraits>) + + OFNH->Header.Size == (char*)FNH) { + // Merge this with a node that is already on the object size free list. + OFNH->Header.Size += Size+sizeof(NodeHeader<PoolTraits>); + return; + } + } + + FNH->Header.Size = Size; + AddNodeToFreeList(Pool, FNH); + return; + + LargeArrayCase: + LargeArrayHeader *LAH = ((LargeArrayHeader*)Node)-1; + DO_IF_TRACE(fprintf(stderr, "%d bytes [large]\n", LAH->Size)); + DO_IF_PNP(CurHeapSize -= LAH->Size); + + // Unlink it from the list of large arrays and free it. + LAH->UnlinkFromList(); + free(LAH); + } + + template<typename PoolTraits> + static void *poolrealloc_internal(PoolTy<PoolTraits> *Pool, void *Node, + unsigned NumBytes) { + DO_IF_TRACE(fprintf(stderr, "[%d] poolrealloc%s(0x%X, %d) -> ", + getPoolNumber(Pool), PoolTraits::getSuffix(), + Node, NumBytes)); + + // If a null pool descriptor is passed in, this is not a pool allocated data + // structure. Hand off to the system realloc. + if (Pool == 0) { + void *Result = realloc(Node, NumBytes); + DO_IF_TRACE(fprintf(stderr, "0x%X (system realloc)\n", Result)); + return Result; + } + if (Node == 0) return poolalloc(Pool, NumBytes); + if (NumBytes == 0) { + poolfree(Pool, Node); + DO_IF_TRACE(fprintf(stderr, "freed\n")); + return 0; + } + + FreedNodeHeader<PoolTraits> *FNH = + (FreedNodeHeader<PoolTraits>*)((char*)Node-sizeof(NodeHeader<PoolTraits>)); + assert((FNH->Header.Size & 1) && "Node not allocated!"); + unsigned Size = FNH->Header.Size & ~1; + if (Size != ~1U) { + // FIXME: This is obviously much worse than it could be. In particular, we + // never try to expand something in a pool. This might hurt some programs! + void *New = poolalloc(Pool, NumBytes); + assert(New != 0 && "Our poolalloc doesn't ever return null for failure!"); + + // Copy the min of the new and old sizes over. + memcpy(New, Node, Size < NumBytes ? Size : NumBytes); + poolfree(Pool, Node); + DO_IF_TRACE(fprintf(stderr, "0x%X (moved)\n", New)); + return New; + } + + // Otherwise, we have a large array. Perform the realloc using the system + // realloc function. This case is actually quite common as many large blocks + // end up being realloc'd it seems. + LargeArrayHeader *LAH = ((LargeArrayHeader*)Node)-1; + LAH->UnlinkFromList(); + + LargeArrayHeader *NewLAH = + (LargeArrayHeader*)realloc(LAH, sizeof(LargeArrayHeader)+NumBytes); + + DO_IF_TRACE(if (LAH == NewLAH) + fprintf(stderr, "resized in place (system realloc)\n"); + else + fprintf(stderr, "0x%X (moved by system realloc)\n", NewLAH+1)); + NewLAH->LinkIntoList(&Pool->LargeArrays); + return NewLAH+1; + } + + unsigned poolobjsize(PoolTy<NormalPoolTraits> *Pool, void *Node) { + if (Node == 0) return 0; + + // If a null pool descriptor is passed in, this is not a pool allocated data + // structure. We don't really have any way to service this!! + if (Pool == 0) { + fprintf(stderr, "ERROR: Cannot call poolobjsize on a pool that is getting" + " memory from the heap. Sorry!\n"); + abort(); + } + + // Check to see how many bytes were allocated to this node. + FreedNodeHeader<NormalPoolTraits> *FNH = + (FreedNodeHeader<NormalPoolTraits>*)((char*)Node - + sizeof(NodeHeader<NormalPoolTraits>)); + assert((FNH->Header.Size & 1) && "Node not allocated!"); + unsigned Size = FNH->Header.Size & ~1; + if (Size != ~1U) return Size; + + // Otherwise, we have a large array. + LargeArrayHeader *LAH = ((LargeArrayHeader*)Node)-1; + return LAH->Size; + } + + + void *poolalloc(PoolTy<NormalPoolTraits> *Pool, unsigned NumBytes) { + DO_IF_FORCE_MALLOCFREE(return malloc(NumBytes)); + void *ret = poolalloc_internal(Pool, NumBytes); + // printf("Allocated in pool %x num bytes %d ret val %x\n",Pool, NumBytes, ret); + return ret; + } + + + void poolfree(PoolTy<NormalPoolTraits> *Pool, void *Node) { + DO_IF_FORCE_MALLOCFREE(free(Node); return); + poolfree_internal(Pool, Node); + } + /* + void poolcheck(PoolTy<NormalPoolTraits> *Pool, void *referrent, void *Node) { + Splay *splay = splay_find_ptr(Pool->splay, (unsigned long) referrent); + if (((unsigned long) referrent) + splay->val < (unsigned long) Node) { + printf("Bounds check failure"); + abort(); + } + } + */ + void *getreferrent(PoolTy<NormalPoolTraits> *Pool, void *referrent) { + return splay_find_ptr(Pool->splay, (unsigned long) referrent); + } + + bool poolcheck4(Splay *splay, void *Node) { + if( ((unsigned long) splay->key) > ((unsigned long)Node)) + return false; + if (((unsigned long) splay->key) + splay->val < (unsigned long) Node) { + return false; + }; + return true; + } + + void* poolcheckslow(PoolTy<NormalPoolTraits> *A, void *B, void *C) { + void *r = getreferrent(A, B); + + if (turn == 1) { + pCache1 = r; + turn = 2; + } else { + pCache2 = r; + turn = 1; + } + if (!poolcheck4((Splay *)r, C)) { + printf("Bounds error \n"); + abort(); + } + return r; + } + + + + void poolregister(PoolTy<NormalPoolTraits> *Pool, void *referrent, unsigned size) { + if (Pool) + splay_insert_ptr(Pool->splay, (unsigned long) referrent, size); + } + + void *poolrealloc(PoolTy<NormalPoolTraits> *Pool, void *Node, + unsigned NumBytes) { + DO_IF_FORCE_MALLOCFREE(return realloc(Node, NumBytes)); + return poolrealloc_internal(Pool, Node, NumBytes); + } + + + + //===----------------------------------------------------------------------===// + // Pointer Compression runtime library. Most of these are just wrappers + // around the normal pool routines. + //===----------------------------------------------------------------------===// + + // For now, use address space reservation of 256MB. + #define POOLSIZE (256*1024*1024) + + // Pools - When we are done with a pool, don't munmap it, keep it around for + // next time. + static PoolSlab<CompressedPoolTraits> *Pools[4] = { 0, 0, 0, 0 }; + + + void *poolinit_pc(PoolTy<CompressedPoolTraits> *Pool, + unsigned DeclaredSize, unsigned ObjAlignment) { + poolinit_internal(Pool, DeclaredSize, ObjAlignment); + + // The number of nodes to stagger in the mmap'ed pool + static unsigned stagger=0; + + // Create the pool. We have to do this eagerly (instead of on the first + // allocation), because code may want to eagerly copy the pool base into a + // register. + + // If we already have a pool mapped, reuse it. + for (unsigned i = 0; i != 4; ++i) + if (Pools[i]) { + Pool->Slabs = Pools[i]; + Pools[i] = 0; + break; + } + + // + // Wrap the stagger value back to zero if we're past the size of the pool. + // This way, we always reserve less than 2*POOLSIZE of the virtual address + // space. + // + if ((stagger * DeclaredSize) >= POOLSIZE) + stagger = 0; + + if (Pool->Slabs == 0) { + // + // Didn't find an existing pool, create one. + // + // To create a pool, we stagger the beginning of the pool so that pools + // do not end up starting on the same page boundary (creating extra cache + // conflicts). + // + Pool->Slabs = (PoolSlab<CompressedPoolTraits>*) + AllocateSpaceWithMMAP(POOLSIZE + (DeclaredSize * stagger), true); + Pool->Slabs += (DeclaredSize * stagger); + + // Increase the stagger amount by one node. + stagger++; + DO_IF_TRACE(fprintf(stderr, "RESERVED ADDR SPACE: %p -> %p\n", + Pool->Slabs, (char*)Pool->Slabs+POOLSIZE)); + } + PoolSlab<CompressedPoolTraits>::create_for_ptrcomp(Pool, Pool->Slabs, + POOLSIZE); + return Pool->Slabs; + } + + void pooldestroy_pc(PoolTy<CompressedPoolTraits> *Pool) { + assert(Pool && "Null pool pointer passed in to pooldestroy!\n"); + if (Pool->Slabs == 0) + return; // no memory allocated from this pool. + + unsigned PID; + #ifdef ENABLE_POOL_IDS + PID = removePoolNumber(Pool); + #endif + DO_IF_TRACE(fprintf(stderr, "[%d] pooldestroy_pc", PID)); + DO_IF_POOLDESTROY_STATS(PrintPoolStats(Pool)); + + // If there is space to remember this pool, do so. + for (unsigned i = 0; i != 4; ++i) + if (Pools[i] == 0) { + Pools[i] = Pool->Slabs; + return; + } + + // Otherwise, just munmap it. + DO_IF_TRACE(fprintf(stderr, "UNMAPPING ADDR SPACE: %p -> %p\n", + Pool->Slabs, (char*)Pool->Slabs+POOLSIZE)); + munmap(Pool->Slabs, POOLSIZE); + } + + unsigned long long poolalloc_pc(PoolTy<CompressedPoolTraits> *Pool, + unsigned NumBytes) { + void *Result = poolalloc_internal(Pool, NumBytes); + return (char*)Result-(char*)Pool->Slabs; + } + + void poolfree_pc(PoolTy<CompressedPoolTraits> *Pool, unsigned long long Node) { + poolfree_internal(Pool, (char*)Pool->Slabs+Node); + } + + + //===----------------------------------------------------------------------===// + // Access Tracing Runtime Library Support + //===----------------------------------------------------------------------===// + + static FILE *FD = 0; + void poolaccesstraceinit() { + #ifdef ALWAYS_USE_MALLOC_FREE + FD = fopen("trace.malloc.csv", "w"); + #else + FD = fopen("trace.pa.csv", "w"); + #endif + } + + #define NUMLRU 2 + static void *LRUWindow[NUMLRU]; + + void poolaccesstrace(void *Ptr, void *PD) { + static unsigned Time = ~0U; + static void *LastPtr = 0; + + // Not pool memory? + if (PD == 0) return; + + // Filter out stuff that is not to the heap. + ++Time; + if ((uintptr_t)Ptr > 1000000000UL) + return; + + Ptr = (void*)((intptr_t)Ptr & ~31L); + + #if 1 + // Drop duplicate points. + for (unsigned i = 0; i != NUMLRU; ++i) + if (Ptr == LRUWindow[i]) { + memmove(LRUWindow+1, LRUWindow, sizeof(void*)*i); + LRUWindow[0] = Ptr; + return; + } + + // Rotate LRU window. + memmove(LRUWindow+1, LRUWindow, sizeof(void*)*(NUMLRU-1)); + LRUWindow[0] = Ptr; + #endif + + // Delete many points to reduce data. + static unsigned int Ctr; + if ((++Ctr & 31)) return; + + + fprintf(FD, "%d", Time); + #if defined(ENABLE_POOL_IDS) + for (unsigned PID = getPoolNumber(PD)+1; PID; --PID) + fprintf(FD,"\t?"); + #else + fprintf(FD, "\t%p ", PD); + #endif + fprintf(FD, "\t%lu\n", (intptr_t)Ptr); + } _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits