safecode/old_runtime/KernelSafePoolAllocator/PoolAllocatorBitMask.cpp

//===- PoolAllocatorBitMask.cpp - Implementation of poolallocator runtime -===//
// 
//                       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.
//
// 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.
//
//===----------------------------------------------------------------------===//

#include "PoolAllocator.h"
#include "PoolCheck.h"
#include "PageManager.h"
#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <unistd.h>
#define DEBUG(x)
#define POOLCHECK(x) x 
//===----------------------------------------------------------------------===//
//
//  PoolSlab implementation
//
//===----------------------------------------------------------------------===//
unsigned ArrayBoundsCheck = 1;

// 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
  PoolSlab * OrigSlab;
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;
  // 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 NodeFlagsVector1;
  bool isNodeAllocated(unsigned NodeNum) {
    unsigned * NodeFlagsVector = &NodeFlagsVector1;
    return NodeFlagsVector[NodeNum/16] & (1 << (NodeNum & 15));
  }

  void markNodeAllocated(unsigned NodeNum) {
    unsigned * NodeFlagsVector = &NodeFlagsVector1;
    NodeFlagsVector[NodeNum/16] |= 1 << (NodeNum & 15);
  }

  void markNodeFree(unsigned NodeNum) {
    unsigned * NodeFlagsVector = &NodeFlagsVector1;
    NodeFlagsVector[NodeNum/16] &= ~(1 << (NodeNum & 15));
  }

  void setStartBit(unsigned NodeNum) {
    unsigned * NodeFlagsVector = &NodeFlagsVector1;
    NodeFlagsVector[NodeNum/16] |= 1 << ((NodeNum & 15)+16);
  }

  bool isStartOfAllocation(unsigned NodeNum) {
    unsigned * NodeFlagsVector = &NodeFlagsVector1;
    return NodeFlagsVector[NodeNum/16] & (1 << ((NodeNum & 15)+16));
  }
  
  void clearStartBit(unsigned NodeNum) {
    unsigned * NodeFlagsVector = &NodeFlagsVector1;
    NodeFlagsVector[NodeNum/16] &= ~(1 << ((NodeNum & 15)+16));
  }

public:
  // create - Create a new (empty) slab and add it to the end of the Pools list.
  static PoolSlab *create(PoolTy *Pool);

  // createSingleArray - Create a slab for a large singlearray with NumNodes
  // entries in it, returning the pointer into the pool directly.
  static void *createSingleArray(PoolTy *Pool, unsigned NumNodes);

  // getSlabSize - Return the number of nodes that each slab should contain.
  static unsigned getSlabSize(PoolTy *Pool) {
    // We need space for the header...
    unsigned NumNodes = PageSize-sizeof(PoolSlab);
    
    // We need space for the NodeFlags...
    unsigned NodeFlagsBytes = NumNodes/Pool->NodeSize * 2 / 8;
    NumNodes -= (NodeFlagsBytes+3) & ~3;  // Round up to int boundaries.

    // Divide the remainder among the nodes!
    return NumNodes / Pool->NodeSize;
  }

  void initialize(unsigned NodesPerSlab) ;
  
  unsigned int GetNumNodesInSlab() {
    return NumNodesInSlab;
  }
  
  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();


  // Unmap - Release the memory for the current object.
  void mprotect();
  
  // 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) {
    unsigned * NodeFlagsVector = &NodeFlagsVector1;
    char *Data = (char*)&NodeFlagsVector[((unsigned)NumNodesInSlab+15)/16];
    return &Data[ElementNum*ElementSize];
  }
  const void *getElementAddress(unsigned ElementNum, unsigned ElementSize)const{
    const unsigned * NodeFlagsVector = &NodeFlagsVector1;
    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);
  
  // 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);
};

// create - Create a new (empty) slab and add it to the end of the Pools list.
PoolSlab *PoolSlab::create(PoolTy *Pool) {
  unsigned NodesPerSlab = getSlabSize(Pool);

  unsigned Size = sizeof(PoolSlab) + 4*((NodesPerSlab+15)/16) +
    Pool->NodeSize*getSlabSize(Pool);
  assert(Size <= PageSize && "Trying to allocate a slab larger than a page!");
  PoolSlab *PS = (PoolSlab*)AllocatePage();

  PS->NumNodesInSlab = NodesPerSlab;
  PS->OrigSlab = PS; 
  PS->isSingleArray = 0;  // Not a single array!
  PS->FirstUnused = 0;    // Nothing allocated.
  PS->UsedBegin   = 0;    // Nothing allocated.
  PS->UsedEnd     = 0;    // Nothing allocated.

  // Add the slab to the list...
  PS->addToList((PoolSlab**)&Pool->Ptr1);
  //  printf(" creating a slab %x\n", PS);
  return PS;
}

void *PoolSlab::createSingleArray(PoolTy *Pool, unsigned NumNodes) {
  // FIXME: This wastes memory by allocating space for the NodeFlagsVector
  unsigned NodesPerSlab = getSlabSize(Pool);
  assert(NumNodes > NodesPerSlab && "No need to create a single array!");

  unsigned NumPages = (NumNodes+NodesPerSlab-1)/NodesPerSlab;
  PoolSlab *PS = (PoolSlab*)AllocateNPages(NumPages);

  assert(PS && "poolalloc: Could not allocate memory!");

  if (Pool->NumSlabs > AddrArrSize)
    Pool->Slabs->insert((void*)PS);
  else if (Pool->NumSlabs == AddrArrSize) {
    // Create the hash_set
    Pool->Slabs = new hash_set<void *>;
    Pool->Slabs->insert((void *)PS);
    for (unsigned i = 0; i < AddrArrSize; ++i)
      Pool->Slabs->insert((void *) Pool->SlabAddressArray[i]);
  } else {
    // Insert it in the array
    Pool->SlabAddressArray[Pool->NumSlabs] = (unsigned) PS;
  }
  Pool->NumSlabs++;
  
  PS->addToList((PoolSlab**)&Pool->LargeArrays);

  PS->isSingleArray = 1;
  PS->OrigSlab = PS;
  PS->NumNodesInSlab = NumPages * PageSize;
  *(unsigned*)&PS->FirstUnused = NumPages;
  return PS->getElementAddress(0, 0);
}
void MprotectPage(void *pa, unsigned numPages);

void PoolSlab::mprotect() {
  if (isSingleArray) {
      unsigned NumPages = *(unsigned*)&FirstUnused; 
      MprotectPage((char*)this, NumPages);
  }
  else 
    MprotectPage(this, 1);
}

void PoolSlab::destroy() {
  if (isSingleArray)
    for (unsigned NumPages = *(unsigned*)&FirstUnused; NumPages != 1;--NumPages)
      FreePage((char*)this + (NumPages-1)*PageSize);

  FreePage(this);
}

// allocateSingle - Allocate a single element from this pool, returning -1 if
// there is no space.
int PoolSlab::allocateSingle() {
  // If the slab is a single array, go on to the next slab.  Don't allocate
  // single nodes in a SingleArray slab.
  if (isSingleArray) return -1;

  unsigned SlabSize = PoolSlab::getSlabSize();

  // Check to see if there are empty entries at the end of the slab...
  if (UsedEnd < SlabSize) {
    // Mark the returned entry used
    unsigned short UE = UsedEnd;
    markNodeAllocated(UE);
    setStartBit(UE);
    
    // If we are allocating out the first unused field, bump its index also
    if (FirstUnused == UE)
      FirstUnused++;
    
    // Return the entry, increment UsedEnd field.
    return UsedEnd++;
  }
  
  // If not, check to see if this node has a declared "FirstUnused" value that
  // is less than the number of nodes allocated...
  //
  if (FirstUnused < SlabSize) {
    // Successfully allocate out the first unused node
    unsigned Idx = FirstUnused;
    markNodeAllocated(Idx);
    setStartBit(Idx);
    
    // Increment FirstUnused to point to the new first unused value...
    // FIXME: this should be optimized
    unsigned short FU = FirstUnused;
    do {
      ++FU;
    } while (FU != SlabSize && isNodeAllocated(FU));
    FirstUnused = FU;
    
    return Idx;
  }
  
  return -1;
}

// allocateMultiple - Allocate multiple contiguous elements from this pool,
// returning -1 if there is no space.
int PoolSlab::allocateMultiple(unsigned Size) {
  // Do not allocate small arrays in SingleArray slabs
  if (isSingleArray) return -1;

  // For small array allocation, check to see if there are empty entries at the
  // end of the slab...
  if (UsedEnd+Size <= getSlabSize()) {
    // Mark the returned entry used and set the start bit
    unsigned UE = UsedEnd;
    setStartBit(UE);
    for (unsigned i = UE; i != UE+Size; ++i)
      markNodeAllocated(i);
    
    // If we are allocating out the first unused field, bump its index also
    if (FirstUnused == UE)
      FirstUnused += Size;

    // Increment UsedEnd
    UsedEnd += Size;

    // Return the entry
    return UE;
  }

  // If not, check to see if this node has a declared "FirstUnused" value
  // starting which Size nodes can be allocated
  //
  unsigned Idx = FirstUnused;
  while (Idx+Size <= getSlabSize()) {
    assert(!isNodeAllocated(Idx) && "FirstUsed is not accurate!");

    // Check if there is a continuous array of Size nodes starting FirstUnused
    unsigned LastUnused = Idx+1;
    for (; LastUnused != Idx+Size && !isNodeAllocated(LastUnused); ++LastUnused)
      /*empty*/;

    // If we found an unused section of this pool which is large enough, USE IT!
    if (LastUnused == Idx+Size) {
      setStartBit(Idx);
      // FIXME: this loop can be made more efficient!
      for (unsigned i = Idx; i != Idx + Size; ++i)
        markNodeAllocated(i);

      // This should not be allocating on the end of the pool, so we don't need
      // to bump the UsedEnd pointer.
      assert(Idx != UsedEnd && "Shouldn't allocate at end of pool!");

      // If we are allocating out the first unused field, bump its index also.
      if (Idx == FirstUnused)
        FirstUnused += Size;
      
      // Return the entry
      return Idx;
    }

    // Otherwise, try later in the pool.  Find the next unused entry.
    Idx = LastUnused;
    while (Idx+Size <= getSlabSize() && isNodeAllocated(Idx))
      ++Idx;
  }

  return -1;
}


// containsElement - Return the element number of the specified address in
// this slab.  If the address is not in slab, return -1.
int PoolSlab::containsElement(void *Ptr, unsigned ElementSize) const {
  const void *FirstElement = getElementAddress(0, 0);
  if (FirstElement <= Ptr) {
    unsigned Delta = (char*)Ptr-(char*)FirstElement;
    if (isSingleArray) 
      if (Delta < NumNodesInSlab) return Delta/ElementSize;
    unsigned Index = Delta/ElementSize;
    if (Index < getSlabSize()) {
      if (Delta % ElementSize != 0) {
	printf("Freeing pointer into the middle of an element!");
	abort();
      }
      
      return Index;
    }
  }
  return -1;
}

void PoolSlab::initialize(unsigned NodesPerSlab) {
  
 NumNodesInSlab = NodesPerSlab;
 isSingleArray = 0;  // Not a single array!
 FirstUnused = 0;    // Nothing allocated.
 UsedBegin   = 0;    // Nothing allocated.
 UsedEnd     = 0;    // Nothing allocated.
  
  // Add the slab to the list...
}
// freeElement - Free the single node, small array, or entire array indicated.
void PoolSlab::freeElement(unsigned short ElementIdx) {
  if (!isNodeAllocated(ElementIdx)) return;
  //  assert(isNodeAllocated(ElementIdx) &&
  //         "poolfree: Attempt to free node that is already freed\n");
  //  assert(!isSingleArray && "Cannot free an element from a single array!");

  // Mark this element as being free!
  markNodeFree(ElementIdx);

  // If this slab is not a SingleArray
  assert(isStartOfAllocation(ElementIdx) &&
         "poolfree: Attempt to free middle of allocated array\n");
  
  // Free the first cell
  clearStartBit(ElementIdx);
  markNodeFree(ElementIdx);
  
  // Free all nodes if this was a small array allocation.
  unsigned short ElementEndIdx = ElementIdx + 1;

  // FIXME: This should use manual strength reduction to produce decent code.
  unsigned short UE = UsedEnd;
  while (ElementEndIdx != UE &&
         !isStartOfAllocation(ElementEndIdx) && 
         isNodeAllocated(ElementEndIdx)) {
    markNodeFree(ElementEndIdx);
    ++ElementEndIdx;
  }
  
  // Update the first free field if this node is below the free node line
  if (ElementIdx < FirstUnused) FirstUnused = ElementIdx;

  // Update the first used field if this node was the first used.
  if (ElementIdx == UsedBegin) UsedBegin = ElementEndIdx;
  
  // If we are freeing the last element in a slab, shrink the UsedEnd marker
  // down to the last used node.
  if (ElementEndIdx == UE) {
#if 0
      printf("FU: %d, UB: %d, UE: %d  FREED: [%d-%d)",
           FirstUnused, UsedBegin, UsedEnd, ElementIdx, ElementEndIdx);
#endif

    // If the user is freeing the slab entirely in-order, it's quite possible
    // that all nodes are free in the slab.  If this is the case, simply reset
    // our pointers.
    if (UsedBegin == UE) {
      //printf(": SLAB EMPTY\n");
      FirstUnused = 0;
      UsedBegin = 0;
      UsedEnd = 0;
    } else if (FirstUnused == ElementIdx) {
      // Freed the last node(s) in this slab.
      FirstUnused = ElementIdx;
      UsedEnd = ElementIdx;
    } else {
      UsedEnd = lastNodeAllocated(ElementIdx);
      assert(FirstUnused <= UsedEnd+1 &&
             "FirstUnused field was out of date!");
    }
  }
}

unsigned PoolSlab::lastNodeAllocated(unsigned ScanIdx) {
  // Check the last few nodes in the current word of flags...
  unsigned CurWord = ScanIdx/16;
  unsigned * NodeFlagsVector = &NodeFlagsVector1;
  unsigned short Flags = NodeFlagsVector[CurWord] & 0xFFFF;
  if (Flags) {
    // Mask off nodes above this one
    Flags &= (1 << ((ScanIdx & 15)+1))-1;
    if (Flags) {
      // If there is still something in the flags vector, then there is a node
      // allocated in this part.  The goto is a hack to get the uncommonly
      // executed code away from the common code path.
      //printf("A: ");
      goto ContainsAllocatedNode;
    }
  }

  // Ok, the top word doesn't contain anything, scan the whole flag words now.
  --CurWord;
  while (CurWord != ~0U) {
    unsigned * NodeFlagsVector = &NodeFlagsVector1;
    Flags = NodeFlagsVector[CurWord] & 0xFFFF;
    if (Flags) {
      // There must be a node allocated in this word!
      //printf("B: ");
      goto ContainsAllocatedNode;
    }
    CurWord--;
  }
  return 0;

ContainsAllocatedNode:
  // Figure out exactly which node is allocated in this word now.  The node
  // allocated is the one with the highest bit set in 'Flags'.
  //
  // This should use __builtin_clz to get the value, but this builtin is only
  // available with GCC 3.4 and above.  :(
  assert(Flags && "Should have allocated node!");
  
  unsigned short MSB;
#if GCC3_4_EVENTUALLY
  MSB = 16 - ::__builtin_clz(Flags);
#else
  for (MSB = 15; (Flags & (1U << MSB)) == 0; --MSB)
    /*empty*/;
#endif

  assert((1U << MSB) & Flags);   // The bit should be set
  assert((~(1U << MSB) & Flags) < Flags);// Removing it should make flag smaller
  ScanIdx = CurWord*16 + MSB;
  assert(isNodeAllocated(ScanIdx));
  return ScanIdx;
}


//===----------------------------------------------------------------------===//
//
//  Pool allocator library implementation
//
//===----------------------------------------------------------------------===//

// poolinit - Initialize a pool descriptor to empty
//
void poolinit(PoolTy *Pool, unsigned NodeSize) {
  assert(Pool && "Null pool pointer passed into poolinit!\n");
  DEBUG(printf("pool init %x, %d\n", Pool, NodeSize);)

  // Ensure the page manager is initialized
  InitializePageManager();

  // We must alway return unique pointers, even if they asked for 0 bytes
  Pool->NodeSize = NodeSize ? NodeSize : 1;
  Pool->Ptr1 = Pool->Ptr2 = 0;
  Pool->LargeArrays = 0;
  // For SAFECode, we set FreeablePool to 0 always
  //  Pool->FreeablePool = 0;
  Pool->lastUsed = 0;
  Pool->prevPage[0] = 0;
  Pool->prevPage[1] = 0;
  // Initialize the SlabAddressArray to zero
  for (int i = 0; i < AddrArrSize; ++i) {
    Pool->SlabAddressArray[i] = 0;
  }

  Pool->NumSlabs = 0;
  POOLCHECK(poolcheckinit(Pool, NodeSize);)
  POOLCHECK(Pool->splay = new_splay();)
  POOLCHECK(Pool->PCS = 0;)
  ///  Pool->Slabs = new hash_set<void*>;
  // Call hash_set constructor explicitly
  //   void *SlabPtr = &Pool->Slabs;
  //   new (SlabPtr) hash_set<void*>;
}

void poolmakeunfreeable(PoolTy *Pool) {
  assert(Pool && "Null pool pointer passed in to poolmakeunfreeable!\n");
  //  Pool->FreeablePool = 0;
}

// pooldestroy - Release all memory allocated for a pool
//
void pooldestroy(PoolTy *Pool) {
  DEBUG(printf("pooldestroying %x\n", Pool);)
  assert(Pool && "Null pool pointer passed in to pooldestroy!\n");
  if (Pool->NumSlabs > AddrArrSize) {
    Pool->Slabs->clear();
    delete Pool->Slabs;
  }
  POOLCHECK(free_splay(Pool->splay);)
  // Free any partially allocated slabs
  PoolSlab *PS = (PoolSlab*)Pool->Ptr1;
  while (PS) {
    PoolSlab *Next = PS->Next;
    PS->destroy();
    PS = Next;
  }

  // Free the completely allocated slabs
  PS = (PoolSlab*)Pool->Ptr2;
  while (PS) {
    PoolSlab *Next = PS->Next;
    PS->destroy();
    PS = Next;
  }

  // Free the large arrays
  PS = (PoolSlab*)Pool->LargeArrays;
  while (PS) {
    PoolSlab *Next = PS->Next;
    PS->destroy();
    PS = Next;
  }

  POOLCHECK(poolcheckdestroy(Pool);)
}


// poolallocarray - a helper function used to implement poolalloc, when the
// number of nodes to allocate is not 1.
static void *poolallocarray(PoolTy* Pool, unsigned Size) {
  assert(Pool && "Null pool pointer passed into poolallocarray!\n");
  if (Size > PoolSlab::getSlabSize(Pool))
    return PoolSlab::createSingleArray(Pool, Size);
 
  PoolSlab *PS = (PoolSlab*)Pool->Ptr1;

  // Loop through all of the slabs looking for one with an opening
  for (; PS; PS = PS->Next) {
    int Element = PS->allocateMultiple(Size);
    if (Element != -1) {
      // We allocated an element.  Check to see if this slab has been completely
      // filled up.  If so, move it to the Ptr2 list.
      if (PS->isFull()) {
        PS->unlinkFromList();
        PS->addToList((PoolSlab**)&Pool->Ptr2);
      }
      return PS->getElementAddress(Element, Pool->NodeSize);
    }
  }
  
  PoolSlab *New = PoolSlab::create(Pool);
  POOLCHECK(poolcheckAddSlab(&Pool->PCS, New);)
  if (Pool->NumSlabs > AddrArrSize) {
    DEBUG(printf("new slab inserting %x \n", (void *)New);)
    Pool->Slabs->insert((void *)New);
  } else if (Pool->NumSlabs == AddrArrSize) {
    // Create the hash_set
    Pool->Slabs = new hash_set<void *>;
    Pool->Slabs->insert((void *)New);
    for (unsigned i = 0; i < AddrArrSize; ++i)
      Pool->Slabs->insert((void *)Pool->SlabAddressArray[i]);
  } else {
    // Insert it in the array
    Pool->SlabAddressArray[Pool->NumSlabs] = (unsigned) New;
  }
  Pool->NumSlabs++;
  
  //  return malloc(Size * Pool->NodeSize);
  int Idx = New->allocateMultiple(Size);
  assert(Idx == 0 && "New allocation didn't return zero'th node?");
  return New->getElementAddress(0, 0);
}

void *poolalloc(PoolTy *Pool, unsigned NumBytes) {
  //  return malloc(Size * Pool->NodeSize);
  void *retAddress = NULL;
  if (!Pool) {
    printf("Null pool pointer passed in to poolalloc!, FAILING\n");
    exit(-1);
  } 
  unsigned NodeSize = Pool->NodeSize;
  unsigned NodesToAllocate1 = NumBytes / NodeSize;
  if (NodesToAllocate1 == 0) {
    //    abort();
  }
  unsigned NodesToAllocate = (NumBytes+NodeSize-1)/NodeSize;
  if (NodesToAllocate > 1) {
    retAddress = poolallocarray(Pool, NodesToAllocate);
    DEBUG(printf("poolalloc: Pool %x NodeSize %d retaddress %x numbytes %d\n",Pool, Pool->NodeSize, retAddress, NumBytes);)
      POOLCHECK(poolcheckregister(Pool->splay, retAddress, NumBytes);)
    return retAddress;
  }

  // Special case the most common situation, where a single node is being
  // allocated.
  PoolSlab *PS = (PoolSlab*)Pool->Ptr1;

  if (__builtin_expect(PS != 0, 1)) {
    int Element = PS->allocateSingle();
    if (__builtin_expect(Element != -1, 1)) {
      // We allocated an element.  Check to see if this slab has been
      // completely filled up.  If so, move it to the Ptr2 list.
      if (__builtin_expect(PS->isFull(), false)) {
        PS->unlinkFromList();
        PS->addToList((PoolSlab**)&Pool->Ptr2);
      }
      retAddress = PS->getElementAddress(Element, NodeSize);
      DEBUG(printf("poolalloc: Pool %x NodeSize %d retaddress %x numbytes %d\n",Pool, Pool->NodeSize, retAddress, NumBytes);)
      POOLCHECK(poolcheckregister(Pool->splay, retAddress, NumBytes);)
      return retAddress;
    }

    // Loop through all of the slabs looking for one with an opening
    for (PS = PS->Next; PS; PS = PS->Next) {
      int Element = PS->allocateSingle();
      if (Element != -1) {
        // We allocated an element.  Check to see if this slab has been
        // completely filled up.  If so, move it to the Ptr2 list.
        if (PS->isFull()) {
          PS->unlinkFromList();
          PS->addToList((PoolSlab**)&Pool->Ptr2);
        }
	retAddress = PS->getElementAddress(Element, NodeSize);
	DEBUG(printf("poolalloc: Pool %x NodeSize %d retaddress %x numbytes %d\n",Pool, Pool->NodeSize, retAddress, NumBytes);)
        POOLCHECK(poolcheckregister(Pool->splay, retAddress, NumBytes);)
	return retAddress;
      }
    }
  }

  // Otherwise we must allocate a new slab and add it to the list
  PoolSlab *New = PoolSlab::create(Pool);
  POOLCHECK(poolcheckAddSlab(&Pool->PCS, New);)
  
  if (Pool->NumSlabs > AddrArrSize)
    Pool->Slabs->insert((void *)New);
  else if (Pool->NumSlabs == AddrArrSize) {
    // Create the hash_set
    Pool->Slabs = new hash_set<void *>;
    Pool->Slabs->insert((void *)New);
    for (unsigned i = 0; i < AddrArrSize; ++i)
      Pool->Slabs->insert((void *)Pool->SlabAddressArray[i]);
  } else {
    // Insert it in the array
    Pool->SlabAddressArray[Pool->NumSlabs] = (unsigned) New;
  }
  Pool->NumSlabs++;

  int Idx = New->allocateSingle();
  assert(Idx == 0 && "New allocation didn't return zero'th node?");
  retAddress = New->getElementAddress(0, 0);
  DEBUG(printf("poolalloc: Pool %x NodeSize %d retaddress %x numbytes %d\n",Pool, Pool->NodeSize, retAddress, NumBytes);)
  POOLCHECK(poolcheckregister(Pool->splay, retAddress, NumBytes);)
  return retAddress;
}

/*
// SearchForContainingSlab - This implementation uses the hash_set as well
// as the array to search the list of allocated slabs for the node in question
static PoolSlab *SearchForContainingSlab(PoolTy *Pool, void *Node,
                                         unsigned &TheIndex) {
  //  printf("in pool check for pool %x, node %x\n",Pool,Node);
  unsigned NodeSize = Pool->NodeSize;
  void *PS;
  if (!Pool) {
    printf("Empty Pool in pool check FAILING \n");
    exit(-1);
  } 
  assert (Pool->AllocadPool <= 0 && "SearchForContainingSlab not to be called"
          " for alloca'ed pools");
  
  PS = (void*)((long)Node & ~(PageSize-1));
  if (Pool->NumSlabs > AddrArrSize) {
    hash_set<void*> &theSlabs = *Pool->Slabs;
    if (theSlabs.find(PS) == theSlabs.end()) {
      // Check the LargeArrays
      if (Pool->LargeArrays) {
	PoolSlab *PSlab = (PoolSlab*) Pool->LargeArrays;
	unsigned Idx = -1;
	while (PSlab) {
	  assert(PSlab && "poolcheck: node being free'd not found in "
		 "allocation pool specified!\n");
	  Idx = PSlab->containsElement(Node, NodeSize);
	  if (Idx != -1) break;
	  PSlab = PSlab->Next;
	}
	if (Idx == -1) {
	  printf("poolcheck: node being checked not found in pool \n");
	  abort();
	}
	TheIndex = Idx;
	return PSlab;
      } else {
	printf("poolcheck: node being checked not found in pool \n");
	abort();
      }
    } else {
      // Check that Node does not point to PoolSlab meta-data
      if ((PoolSlab *)PS->getElementAddress(0,0) > (long) Node) {
	printf("poolcheck: node being checked points to meta-data \n");
	abort();
      }	
      TheIndex = PS->containsElement(Node, NodeSize);
      return (PoolSlab *)PS;
    }
  } else {
    bool found;
    for (unsigned i = 0; i < AddrArrSize && !found; ++i) {
      if (Pool->SlabAddressArray[i] == (unsigned) PS)
	found = true;
    } 

    if (found) {
      // Check that Node does not point to PoolSlab meta-data
      if ((PoolSlab *)PS->getElementAddress(0,0) > (long) Node) {
	printf("poolcheck: node being checked points to meta-data \n");
	abort();
      }	
      TheIndex = PS->containsElement(Node, NodeSize);
      return (PoolSlab *)PS;
    } else {
      // Check the LargeArrays
      if (Pool->LargeArrays) {
	PoolSlab *PSlab = (PoolSlab*) Pool->LargeArrays;
	unsigned Idx = -1;
	while (PSlab) {
	  assert(PSlab && "poolcheck: node being free'd not found in "
		 "allocation pool specified!\n");
	  Idx = PSlab->containsElement(Node, NodeSize);
	  if (Idx != -1) break;
	  PSlab = PSlab->Next;
	}
	if (Idx == -1) {
	  printf("poolcheck: node being checked not found in pool \n");
	  abort();
	}
	TheIndex = Idx;
	return PSlab;	
      }
      printf("poolcheck: node being checked not found in pool \n");
      abort();
    }
  }
}
*/

#if 0
// SearchForContainingSlab - Do a brute force search through the list of
// allocated slabs for the node in question.
//
static PoolSlab *SearchForContainingSlab(PoolTy *Pool, void *Node,
                                         unsigned &TheIndex) {
  PoolSlab *PS = (PoolSlab*)Pool->Ptr1;
  unsigned NodeSize = Pool->NodeSize;

  // Search the partially allocated slab list for the slab that contains this
  // node.
  int Idx = -1;
  if (PS) {               // Pool->Ptr1 could be null if Ptr2 isn't
    for (; PS; PS = PS->Next) {
      Idx = PS->containsElement(Node, NodeSize);
      if (Idx != -1) break;
    }
  }

  // If the partially allocated slab list doesn't contain it, maybe the
  // completely allocated list does.
  if (PS == 0) {
    PS = (PoolSlab*)Pool->Ptr2;
    assert(Idx == -1 && "Found node but don't have PS?");
    
    while (PS) {
      assert(PS && "poolfree: node being free'd not found in allocation "
             " pool specified!\n");
      Idx = PS->containsElement(Node, NodeSize);
      if (Idx != -1) break;
      PS = PS->Next;
    }
  }
  
  // Otherwise, maybe its a block within LargeArrays
  if(PS == 0) {
    PS = (PoolSlab*)Pool->LargeArrays;
    assert(Idx == -1  && "Found node but don't have PS?");
    
    while (PS) {
      assert(PS && "poolfree: node being free'd not found in allocation "
             " pool specified!\n");
      Idx = PS->containsElement(Node, NodeSize);
      if (Idx != -1) break;
      PS = PS->Next;
    }
  }

  TheIndex = Idx;
  return PS;
}
#endif

void* poolallocatorcheck(PoolTy *Pool, void *Node) {
  PoolSlab *PS = (PoolSlab*)((unsigned)Node & ~(PageSize-1));

  if (Pool->NumSlabs > AddrArrSize) {
    hash_set<void*> &theSlabs = *Pool->Slabs;
    if (theSlabs.find((void*)PS) == theSlabs.end()) {
      // Check the LargeArrays
      if (Pool->LargeArrays) {
	PoolSlab *PSlab = (PoolSlab*) Pool->LargeArrays;
	int Idx = -1;
	while (PSlab) {
	  assert(PSlab && "poolcheck: node being free'd not found in "
		 "allocation pool specified!\n");
	  Idx = PSlab->containsElement(Node, Pool->NodeSize);
	  if (Idx != -1) {
	    Pool->prevPage[Pool->lastUsed] = PS;
	    Pool->lastUsed = (Pool->lastUsed + 1) % 4;
	    return PS;
	    break;
	  }
	  PSlab = PSlab->Next;
	}
	
	if (Idx == -1) {
	  Splay *ref = splay_find_ptr(Pool->splay, (unsigned long) Node);
	  if (ref)   {
	    return 0;
	  }
	  printf("poolcheck1: node being checked not found in pool with right"
		 " alignment\n");
	  abort();
	} else {
	  return 0;
	  //exit(-1);
	}
      } else {
	// here we check for the splay tree
	Splay *ref = splay_find_ptr(Pool->splay, (unsigned long) Node);
	if (ref) {
	  return 0;
	} else {
	  printf("poolcheck2: ref not found "
		 " alignment\n");
	  abort();
	  exit(-1);
	}
      }
    } else {
      unsigned long startaddr = (unsigned long)PS->getElementAddress(0,0);
      if (startaddr > (unsigned long) Node) {
	printf("poolcheck: node being checked points to meta-data \n");
	abort();
      }
      unsigned long offset = ((unsigned long) Node - (unsigned long) startaddr) % Pool->NodeSize;
      if (offset != 0) {
	printf("poolcheck3: node being checked does not have right alignment\n");
	abort();
      }
      Pool->prevPage[Pool->lastUsed] = PS;
      Pool->lastUsed = (Pool->lastUsed + 1) % 4;
      return PS;
    }
  } else {
    bool found = false;
    for (unsigned i = 0; i < AddrArrSize && !found; ++i) {
      if ((unsigned)Pool->SlabAddressArray[i] == (unsigned) PS) {
	found = true;
	Pool->prevPage[Pool->lastUsed] = PS;
	Pool->lastUsed = (Pool->lastUsed + 1) % 4;
      }
    } 

    if (found) {
      // Check that Node does not point to PoolSlab meta-data
      unsigned long startaddr = (unsigned long)PS->getElementAddress(0,0);
      if (startaddr > (unsigned long) Node) {
	printf("poolcheck: node being checked points to meta-data \n");
	exit(-1);
      }
      unsigned long offset = ((unsigned long) Node - (unsigned long) startaddr) % Pool->NodeSize;
      if (offset != 0) {
	printf("poolcheck4: node being checked does not have right alignment\n");
	abort();
      }
      return PS;
    } else {
      // Check the LargeArrays
      if (Pool->LargeArrays) {
	PoolSlab *PSlab = (PoolSlab*) Pool->LargeArrays;
	int Idx = -1;
	while (PSlab) {
	  assert(PSlab && "poolcheck: node being free'd not found in "
		 "allocation pool specified!\n");
	  Idx = PSlab->containsElement(Node, Pool->NodeSize);
	  if (Idx != -1) {
	    Pool->prevPage[Pool->lastUsed] = PS;
	    Pool->lastUsed = (Pool->lastUsed + 1) % 4;
	    break;
	  }
	  PSlab = PSlab->Next;
	}
	if (Idx == -1) {
	  Splay *ref = splay_find_ptr(Pool->splay, (unsigned long) Node);
	  if (ref)    return 0;	  
	  printf("poolcheck6: node being checked not found in pool with right"
		 " alignment\n");
	  abort();
	} else {
	  return PSlab;
	}
      } else {
	Splay *ref = splay_find_ptr(Pool->splay, (unsigned long) Node);
	if (ref) {
	  return 0;
	} else {
	  printf("poolcheck5: ref not found "
		 " alignment check not done \n");
	  abort();
	}	
      }
    }
  }
}

/*
void poolcheckarray(MetaPoolTy **MP, void *NodeSrc, void *NodeResult) {
  MetaPoolTy *MetaPool = *MP;
  if (!MetaPool) {
    printf("Empty meta pool? \n");
    exit(-1);
  }
  //iteratively search through the list
  //Check if there are other efficient data structures.
  hash_set<void *>::iterator PTI = MetaPool->PoolTySet->begin(), PTE = MetaPool->PoolTySet->end();
  PoolTy *srcPool = 0;
  for (; PTI != PTE; ++PTI) {
    PoolTy *Pool = (PoolTy *)*PTI;
    PoolSlab *PS;
    PS = (PoolSlab*)((unsigned long)NodeSrc & ~(PageSize-1));
    if (Pool->prevPage[0] == PS) {
      srcPool = Pool;
    }
    if (Pool->prevPage[1] == PS) {
      srcPool = Pool;
    }    
    if (Pool->prevPage[2] == PS) {
      srcPool = Pool;
    }    
    if (Pool->prevPage[3] == PS) {
      srcPool = Pool;
    }
    if (poolcheckoptim(Pool, NodeSrc)) {
      srcPool = Pool;
    } else continue;
    //Now check for reuslt
    if (poolcheckoptim(srcPool, NodeResult)) {          
        MetaPool->cachePool = srcPool;
        return;
    } else {
        printf("source and dest belong to different pools\n");
        exit(-1);
    }
  }
  printf("poolcheck failure \n");
  exit(-1);
}
*/

void poolfree(PoolTy *Pool, void *Node) {
  assert(Pool && "Null pool pointer passed in to poolfree!\n");
  DEBUG(printf("poolfree  %x %x \n",Pool,Node);)
  PoolSlab *PS;
  int Idx;
  PS = (PoolSlab *)poolallocatorcheck(Pool, Node);
  assert(PS && "poolfree the element not in pool ");
  if (PS->isSingleArray) {
    PS->unlinkFromList();
    unsigned  NumPages = PS->GetNumNodesInSlab() / PageSize;
    
    unsigned NodesPerSlab = PoolSlab::getSlabSize(Pool);

    unsigned Size = sizeof(PoolSlab) + 4*((NodesPerSlab+15)/16) +
      Pool->NodeSize* NodesPerSlab;
    assert(Size <= PageSize && "Trying to allocate a slab larger than a page!");
    for (unsigned i = 0; i <NumPages; ++i) {
      PoolSlab *PSi = (PoolSlab *)((unsigned long)PS + i * PageSize);

      PSi->initialize(NodesPerSlab);
      if (i != 0) {
	PSi->addToList((PoolSlab**)&Pool->Ptr1);
      }
      if (Pool->NumSlabs > AddrArrSize) {
	DEBUG(printf("new slab inserting %x \n", (void *)New);)
	  Pool->Slabs->insert((void *)PSi);
      } else if (Pool->NumSlabs == AddrArrSize) {
	// Create the hash_set
	Pool->Slabs = new hash_set<void *>;
	Pool->Slabs->insert((void *)PSi);
	for (unsigned i = 0; i < AddrArrSize; ++i)
	  Pool->Slabs->insert((void *)Pool->SlabAddressArray[i]);
      } else {
	// Insert it in the array
	Pool->SlabAddressArray[Pool->NumSlabs] = (unsigned) PSi;
      }
      Pool->NumSlabs++;       
    }
    return;
  } 
  Idx = PS->containsElement(Node, Pool->NodeSize);
  assert((Idx != -1) && " node not present, it should have aborted ");

  // If PS was full, it must have been in list #2.  Unlink it and move it to
  // list #1.
  if (PS->isFull()) {
    // Now that we found the node, we are about to free an element from it.
    // This will make the slab no longer completely full, so we must move it to
    // the other list!
    PS->unlinkFromList(); // Remove it from the Ptr2 list.

    PoolSlab **InsertPosPtr = (PoolSlab**)&Pool->Ptr1;

    // If the partially full list has an empty node sitting at the front of the
    // list, insert right after it.
    if (*InsertPosPtr && (*InsertPosPtr)->isEmpty())
      InsertPosPtr = &(*InsertPosPtr)->Next;

    PS->addToList(InsertPosPtr);     // Insert it now in the Ptr1 list.
  }

  // Free the actual element now!
  PS->freeElement(Idx);

  // Ok, if this slab is empty, we unlink it from the of slabs and either move
  // it to the head of the list, or free it, depending on whether or not there
  // is already an empty slab at the head of the list.
  //
  if (PS->isEmpty()) {
    PS->unlinkFromList();   // Unlink from the list of slabs...
    
    // If we can free this pool, check to see if there are any empty slabs at
    // the start of this list.  If so, delete the FirstSlab!
    PoolSlab *FirstSlab = (PoolSlab*)Pool->Ptr1;
    if (0 && FirstSlab && FirstSlab->isEmpty()) {
      // Here we choose to delete FirstSlab instead of the pool we just freed
      // from because the pool we just freed from is more likely to be in the
      // processor cache.
      FirstSlab->unlinkFromList();
      FirstSlab->destroy();
      //      Pool->Slabs.erase((void *)FirstSlab);
    }
 
    // Link our slab onto the head of the list so that allocations will find it
    // efficiently.    
    PS->addToList((PoolSlab**)&Pool->Ptr1);
  }
}


  void *poolrealloc(PoolTy *Pool, void *Node, unsigned NumBytes) {
    if (Node == 0) return poolalloc(Pool, NumBytes);
    if (NumBytes == 0) {
      poolfree(Pool, Node);
      return 0;
    }
    void *New = poolalloc(Pool, NumBytes);
    //    unsigned Size =
    //FIXME the following may not work in all cases  
    memcpy(New, Node, NumBytes);
    poolfree(Pool, Node);
    return New;
  }

  void poolregister(PoolTy *Pool, void *allocadptr, unsigned NumBytes) {
    POOLCHECK(poolcheckregister(Pool->splay, allocadptr, NumBytes);)
  }
  PoolCheckSlab *poolcheckslab(void *Pool) {
    return ((PoolTy *)Pool)->PCS;
  }

  Splay *poolchecksplay(void *Pool) {
    return ((PoolTy *)Pool)->splay;
  }

  void poolcheckfail (const char * msg) {
    fprintf (stderr, msg);
    fflush (stderr);
    exit (-1);
  }

  void * poolcheckmalloc (unsigned int size) {
    return malloc (size);
  }