| //===- PoolSlab.h - --*- C++ -*--------------------------------------------===// |
| // |
| // The SAFECode Compiler |
| // |
| // 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 declares the interfaces of slabs which used by pool allocators. |
| // |
| // This uses the 'Ptr1' field to maintain a linked list of slabs that are either |
| // empty or are partially allocated from. The 'Ptr2' field of the PoolTy is |
| // used to track a linked list of slabs which are full, ie, all elements have |
| // been allocated from them. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef _POOLSLAB_H_ |
| #define _POOLSLAB_H_ |
| |
| #include "safecode/SAFECode.h" |
| #include "safecode/Runtime/BitmapAllocator.h" |
| #include "safecode/Runtime/PageManager.h" |
| |
| #include <cassert> |
| |
| NAMESPACE_SC_BEGIN |
| |
| //===----------------------------------------------------------------------===// |
| // |
| // PoolSlab implementation |
| // |
| //===----------------------------------------------------------------------===// |
| |
| // PoolSlab Structure - Hold multiple objects of the current node type. |
| // Invariants: FirstUnused <= UsedEnd |
| // |
| struct PoolSlab { |
| PoolSlab **PrevPtr, *Next; |
| bool isSingleArray; // If this slab is used for exactly one array |
| unsigned allocated; // Number of bytes allocated |
| PoolSlab * Canonical; // For stack slabs, the canonical page |
| |
| private: |
| // FirstUnused - First empty node in slab |
| unsigned short FirstUnused; |
| |
| // UsedBegin - The first node in the slab that is used. |
| unsigned short UsedBegin; |
| |
| // UsedEnd - 1 past the last allocated node in slab. 0 if slab is empty |
| unsigned short UsedEnd; |
| |
| // NumNodesInSlab - This contains the number of nodes in this slab, which |
| // effects the size of the NodeFlags vector, and indicates the number of nodes |
| // which are in the slab. |
| unsigned int NumNodesInSlab; |
| |
| // Size of Slab - For single array slabs, specifies the size of the slab in |
| // bytes from beginning to end (including slab header). |
| // |
| public: |
| unsigned int SizeOfSlab; |
| |
| private: |
| // NodeFlagsVector - This array contains two bits for each node in this pool |
| // slab. The first (low address) bit indicates whether this node has been |
| // allocated, and the second (next higher) bit indicates whether this is the |
| // start of an allocation. |
| // |
| // This is a variable sized array, which has 2*NumNodesInSlab bits (rounded up |
| // to 4 bytes). |
| unsigned NodeFlagsVector[1]; |
| |
| bool isNodeAllocated(unsigned NodeNum) { |
| return NodeFlagsVector[NodeNum/16] & (1 << (NodeNum & 15)); |
| } |
| |
| void markNodeAllocated(unsigned NodeNum) { |
| NodeFlagsVector[NodeNum/16] |= 1 << (NodeNum & 15); |
| } |
| |
| void markNodeFree(unsigned NodeNum) { |
| NodeFlagsVector[NodeNum/16] &= ~(1 << (NodeNum & 15)); |
| } |
| |
| void setStartBit(unsigned NodeNum) { |
| NodeFlagsVector[NodeNum/16] |= 1 << ((NodeNum & 15)+16); |
| } |
| |
| public: |
| bool isStartOfAllocation(unsigned NodeNum) { |
| return NodeFlagsVector[NodeNum/16] & (1 << ((NodeNum & 15)+16)); |
| } |
| |
| private: |
| void clearStartBit(unsigned NodeNum) { |
| NodeFlagsVector[NodeNum/16] &= ~(1 << ((NodeNum & 15)+16)); |
| } |
| |
| void assertOkay (void) { |
| assert (FirstUnused <= UsedEnd); |
| assert ((UsedEnd == getSlabSize()) || (!isNodeAllocated(UsedEnd))); |
| assert ((FirstUnused == getSlabSize()) || (!isNodeAllocated(FirstUnused))); |
| } |
| public: |
| // create - Create a new (empty) slab and add it to the end of the Pools list. |
| static PoolSlab *create(BitmapPoolTy *Pool); |
| |
| // createSingleArray - Create a slab for a large singlearray with NumNodes |
| // entries in it, returning the pointer into the pool directly. |
| static void *createSingleArray(BitmapPoolTy *Pool, unsigned NumNodes); |
| |
| // getSlabSize - Return the number of nodes that each slab should contain. |
| static unsigned getSlabSize(BitmapPoolTy *Pool) { |
| // We need space for the header... |
| unsigned NumNodes = PageSize-sizeof(PoolSlab); |
| |
| // We need space for the NodeFlags... |
| // FIXME: |
| // We unconditionally round up a byte. We should only do that if |
| // necessary. |
| unsigned NodeFlagsBytes = (NumNodes/Pool->NodeSize * 2 / 8) + 1; |
| NumNodes -= (NodeFlagsBytes+3) & ~3; // Round up to int boundaries. |
| |
| // Divide the remainder among the nodes! |
| return NumNodes / Pool->NodeSize; |
| } |
| |
| void addToList(PoolSlab **PrevPtrPtr) { |
| PoolSlab *InsertBefore = *PrevPtrPtr; |
| *PrevPtrPtr = this; |
| PrevPtr = PrevPtrPtr; |
| Next = InsertBefore; |
| if (InsertBefore) InsertBefore->PrevPtr = &Next; |
| } |
| |
| void unlinkFromList() { |
| *PrevPtr = Next; |
| if (Next) Next->PrevPtr = PrevPtr; |
| } |
| |
| unsigned getSlabSize() const { |
| return NumNodesInSlab; |
| } |
| |
| // destroy - Release the memory for the current object. |
| void destroy(); |
| |
| // isEmpty - This is a quick check to see if this slab is completely empty or |
| // not. |
| bool isEmpty() const { return UsedEnd == 0; } |
| |
| // isFull - This is a quick check to see if the slab is completely allocated. |
| // |
| bool isFull() const { return isSingleArray || (FirstUnused == getSlabSize()); } |
| |
| // allocateSingle - Allocate a single element from this pool, returning -1 if |
| // there is no space. |
| int allocateSingle(); |
| |
| // allocateMultiple - Allocate multiple contiguous elements from this pool, |
| // returning -1 if there is no space. |
| int allocateMultiple(unsigned Num); |
| |
| // getElementAddress - Return the address of the specified element. |
| void *getElementAddress(unsigned ElementNum, unsigned ElementSize) { |
| char *Data = (char*)&NodeFlagsVector[((unsigned)NumNodesInSlab+15)/16]; |
| return &Data[ElementNum*ElementSize]; |
| } |
| |
| const void *getElementAddress(unsigned ElementNum, unsigned ElementSize)const{ |
| const char *Data = |
| (const char *)&NodeFlagsVector[(unsigned)(NumNodesInSlab+15)/16]; |
| return &Data[ElementNum*ElementSize]; |
| } |
| |
| // containsElement - Return the element number of the specified address in |
| // this slab. If the address is not in slab, return -1. |
| int containsElement(void *Ptr, unsigned ElementSize) const; |
| |
| // freeElement - Free the single node, small array, or entire array indicated. |
| void freeElement(unsigned short ElementIdx); |
| |
| // getSize --- size of an allocation |
| unsigned getSize(void *Node, unsigned ElementSize); |
| |
| // lastNodeAllocated - Return one past the last node in the pool which is |
| // before ScanIdx, that is allocated. If there are no allocated nodes in this |
| // slab before ScanIdx, return 0. |
| unsigned lastNodeAllocated(unsigned ScanIdx); |
| }; |
| |
| //===----------------------------------------------------------------------===// |
| // |
| // StackSlab implementation |
| // |
| //===----------------------------------------------------------------------===// |
| |
| // |
| // Structure: StackSlab |
| // |
| // Description: |
| // A stack slab is similar to a pool slab but simple and smaller. It is used |
| // for stack allocations that have been promoted to the heap. |
| struct StackSlab { |
| public: |
| // Pointer to canonical address of stack slab |
| StackSlab * Canonical; |
| |
| // Pointers for linking in the stack slab |
| StackSlab **PrevPtr, *Next; |
| |
| // Top of stack |
| unsigned int * tos; |
| |
| // Data for the stack |
| unsigned int data[1020]; |
| |
| static StackSlab *create (void * p) { |
| StackSlab *SS = (StackSlab*) p; |
| SS->tos = &(SS->data[0]); |
| return SS; |
| } |
| |
| unsigned char * allocate (unsigned int size) { |
| // |
| // We will return a pointer to the current top of stack. |
| // |
| unsigned char * retvalue = (unsigned char *) (tos); |
| |
| // |
| // Adjust the top of stack down to the next free object. |
| // |
| size = (size + 3) & (~3u); |
| unsigned int NumberOfInts = size / sizeof (unsigned int); |
| tos += NumberOfInts; |
| assert (tos < &(data[1020])); |
| return retvalue; |
| } |
| |
| void clear (void) { |
| tos = data; |
| } |
| |
| void addToList(StackSlab **PrevPtrPtr) { |
| StackSlab *InsertBefore = *PrevPtrPtr; |
| *PrevPtrPtr = this; |
| PrevPtr = PrevPtrPtr; |
| Next = InsertBefore; |
| if (InsertBefore) InsertBefore->PrevPtr = &Next; |
| } |
| |
| void unlinkFromList() { |
| *PrevPtr = Next; |
| if (Next) Next->PrevPtr = PrevPtr; |
| } |
| }; |
| |
| NAMESPACE_SC_END |
| #endif |