///-*-C++-*-////////////////////////////////////////////////////////////////////// Hoard: A Fast, Scalable, and Memory-Efficient Allocator//        for Shared-Memory Multiprocessors// Contact author: Emery Berger, http://www.cs.utexas.edu/users/emery//// Copyright (c) 1998-2000, The University of Texas at Austin.//// This library is free software; you can redistribute it and/or modify// it under the terms of the GNU Library General Public License as// published by the Free Software Foundation, http://www.fsf.org.//// This library is distributed in the hope that it will be useful, but// WITHOUT ANY WARRANTY; without even the implied warranty of// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU// Library General Public License for more details./////////////////////////////////////////////////////////////////////////////////*  heap.h  ------------------------------------------------------------------------  hoardHeap, the base class for threadHeap and processHeap.  ------------------------------------------------------------------------  @(#) $Id: heap.h,v 1.69 2001/03/22 22:10:36 emery Exp $  ------------------------------------------------------------------------  Emery Berger                    | <http://www.cs.utexas.edu/users/emery>  Department of Computer Sciences |             <http://www.cs.utexas.edu>  University of Texas at Austin   |                <http://www.utexas.edu>  ========================================================================*/#ifndef _HEAP_H_#define _HEAP_H_#include "config.h"//include <assert.h>//#include <math.h>#include "arch-specific.h"#include "superblock.h"#include "heapstats.h"class processHeap; // forward declarationclass hoardHeap {public:  hoardHeap (void);  // A superblock that holds more than one object must hold at least  // this many bytes.  enum { SUPERBLOCK_SIZE = 8192 };  // A thread heap must be at least 1/EMPTY_FRACTION empty before we  // start returning superblocks to the process heap.  enum { EMPTY_FRACTION = SUPERBLOCK_FULLNESS_GROUP - 1 };  // Reset value for the least-empty bin.  The last bin  // (SUPERBLOCK_FULLNESS_GROUP-1) is for completely full superblocks,  // so we use the next-to-last bin.  enum { RESET_LEAST_EMPTY_BIN = SUPERBLOCK_FULLNESS_GROUP - 2 };  // The number of empty superblocks that we allow any thread heap to  // hold once the thread heap has fallen below 1/EMPTY_FRACTION  // empty.  enum { MAX_EMPTY_SUPERBLOCKS = EMPTY_FRACTION };  // The maximum number of thread heaps we allow.  (NOT the maximum  // number of threads -- Hoard imposes no such limit.)  This must be  // a power of two! NB: This number is twice the maximum number of  // PROCESSORS supported by Hoard.  enum { MAX_HEAPS = 128 };  // ANDing with this rounds to MAX_HEAPS.  enum { MAX_HEAPS_MASK = MAX_HEAPS - 1 };  //  // The number of size classes.  This combined with the  // SIZE_CLASS_BASE determine the maximum size of an object.  //  // NB: Once this is changed, you must execute maketable.cpp and put  // the generated values into heap.cpp.#if MAX_INTERNAL_FRAGMENTATION == 2  enum { SIZE_CLASSES = 115 };#elif MAX_INTERNAL_FRAGMENTATION == 6  enum { SIZE_CLASSES = 46 };#elif MAX_INTERNAL_FRAGMENTATION == 10  enum { SIZE_CLASSES = 32 };#else#error "Undefined size class base."#endif  // Every object is aligned so that it can always hold a double.  enum { ALIGNMENT = sizeof(double) };  // ANDing with this rounds to ALIGNMENT.  enum { ALIGNMENT_MASK = ALIGNMENT - 1};  // Used for sanity checking.  enum { HEAP_MAGIC = 0x0badcafe };  // Get the usage and allocated statistics.  inline void getStats (int sizeclass, int& U, int& A);#if HEAP_STATS  // How much is the maximum ever in use for this size class?  inline int maxInUse (int sizeclass);  // How much is the maximum memory allocated for this size class?  inline int maxAllocated (int sizeclass);#endif  // Insert a superblock into our list.  void insertSuperblock (int sizeclass,			 superblock * sb,			 processHeap * pHeap);  // Remove the superblock with the most free space.  superblock * removeMaxSuperblock (int sizeclass);  // Find an available superblock (i.e., with some space in it).  inline superblock * findAvailableSuperblock (int sizeclass,					       block *& b,					       processHeap * pHeap);  // Lock this heap.  inline void lock (void);  // Unlock this heap.  inline void unlock (void);  // Set our index number (which heap we are).  inline void setIndex (int i);  // Get our index number (which heap we are).  inline int getIndex (void);  // Free a block into a superblock.  // This is used by processHeap::free().  // Returns 1 iff the superblock was munmapped.  int freeBlock (block *& b,		 superblock *& sb,		 int sizeclass,		 processHeap * pHeap);  //// Utility functions ////  // Return the size class for a given size.  inline static int sizeClass (const size_t sz);  // Return the size corresponding to a given size class.  inline static size_t sizeFromClass (const int sizeclass);  // Return the release threshold corresponding to a given size class.  inline static int getReleaseThreshold (const int sizeclass);  // Return how many blocks of a given size class fit into a superblock.  inline static int numBlocks (const int sizeclass);  // Align a value.  inline static size_t align (const size_t sz);private:  // Disable copying and assignment.  hoardHeap (const hoardHeap&);  const hoardHeap& operator= (const hoardHeap&);  // Recycle a superblock.  inline void recycle (superblock *);  // Reuse a superblock (if one is available).  inline superblock * reuse (int sizeclass);  // Remove a particular superblock.  void removeSuperblock (superblock *, int sizeclass);  // Move a particular superblock from one bin to another.  void moveSuperblock (superblock *,		       int sizeclass,		       int fromBin,		       int toBin);  // Update memory in-use and allocated statistics.  // (*UStats = just update U.)  inline void incStats (int sizeclass, int updateU, int updateA);  inline void incUStats (int sizeclass);  inline void decStats (int sizeclass, int updateU, int updateA);  inline void decUStats (int sizeclass);  //// Members ////#if HEAP_DEBUG  // For sanity checking.  const unsigned long _magic;#else  #define _magic HEAP_MAGIC#endif  // Heap statistics.  heapStats	_stats[SIZE_CLASSES];  // The per-heap lock.  hoardLockType _lock;  // Which heap this is (0 = the process (global) heap).  int _index;  // Reusable superblocks.  superblock *	_reusableSuperblocks;  int		_reusableSuperblocksCount;  // Lists of superblocks.  superblock *	_superblocks[SUPERBLOCK_FULLNESS_GROUP][SIZE_CLASSES];  // The current least-empty superblock bin.  int	_leastEmptyBin[SIZE_CLASSES];  // The lookup table for size classes.  static size_t	_sizeTable[SIZE_CLASSES];  // The lookup table for release thresholds.  static size_t	_threshold[SIZE_CLASSES];public:  // A little helper class that we use to define some statics.  class _initNumProcs {  public:  	_initNumProcs(void);  };  friend class _initNumProcs;protected:  // number of CPUs, cached  static int _numProcessors;  static int _numProcessorsMask;};void hoardHeap::incStats (int sizeclass, int updateU, int updateA) {  assert (_magic == HEAP_MAGIC);  assert (updateU >= 0);  assert (updateA >= 0);  assert (sizeclass >= 0);  assert (sizeclass < SIZE_CLASSES);  _stats[sizeclass].incStats (updateU, updateA);}void hoardHeap::incUStats (int sizeclass) {  assert (_magic == HEAP_MAGIC);  assert (sizeclass >= 0);  assert (sizeclass < SIZE_CLASSES);  _stats[sizeclass].incUStats ();}void hoardHeap::decStats (int sizeclass, int updateU, int updateA) {  assert (_magic == HEAP_MAGIC);  assert (updateU >= 0);  assert (updateA >= 0);  assert (sizeclass >= 0);  assert (sizeclass < SIZE_CLASSES);  _stats[sizeclass].decStats (updateU, updateA);}void hoardHeap::decUStats (int sizeclass){  assert (_magic == HEAP_MAGIC);  assert (sizeclass >= 0);  assert (sizeclass < SIZE_CLASSES);  _stats[sizeclass].decUStats();}void hoardHeap::getStats (int sizeclass, int& U, int& A) {  assert (_magic == HEAP_MAGIC);  assert (sizeclass >= 0);  assert (sizeclass < SIZE_CLASSES);  _stats[sizeclass].getStats (U, A);}#if HEAP_STATSint hoardHeap::maxInUse (int sizeclass) {  assert (_magic == HEAP_MAGIC);  return _stats[sizeclass].getUmax();}int hoardHeap::maxAllocated (int sizeclass) {  assert (_magic == HEAP_MAGIC);  return _stats[sizeclass].getAmax();}#endifsuperblock * hoardHeap::findAvailableSuperblock (int sizeclass,						 block *& b,						 processHeap * pHeap){  assert (this);  assert (_magic == HEAP_MAGIC);  assert (sizeclass >= 0);  assert (sizeclass < SIZE_CLASSES);  superblock * sb = NULL;  int reUsed = 0;  // Look through the superblocks, starting with the almost-full ones  // and going to the emptiest ones.  The Least Empty Bin for a  // sizeclass is a conservative approximation (fixed after one  // iteration) of the first bin that has superblocks in it, starting  // with (surprise) the least-empty bin.  for (int i = _leastEmptyBin[sizeclass]; i >= 0; i--) {    sb = _superblocks[i][sizeclass];    if (sb == NULL) {      if (i == _leastEmptyBin[sizeclass]) {	// There wasn't a superblock in this bin,	// so we adjust the least empty bin.	_leastEmptyBin[sizeclass]--;      }    } else if(sb->getNumAvailable() > 0){      assert (sb->getOwner() == this);      break;    }    sb = NULL;  }#if 1  if (sb == NULL) {    // Try to reuse a superblock.    sb = reuse (sizeclass);    if (sb) {      assert (sb->getOwner() == this);      reUsed = 1;    }  }#endif  if (sb != NULL) {    // Sanity checks:    //   This superblock is 'valid'.    assert (sb->isValid());    //   This superblock has the right ownership.    assert (sb->getOwner() == this);    int oldFullness = sb->getFullness();    // Now get a block from the superblock.    // This superblock must have space available.    b = sb->getBlock();    assert (b != NULL);    // Update the stats.    incUStats (sizeclass);    if (reUsed) {      insertSuperblock (sizeclass, sb, pHeap);      // Fix the stats (since insert will just have incremented them      // by this amount).      decStats (sizeclass,		sb->getNumBlocks() - sb->getNumAvailable(),		sb->getNumBlocks());    } else {      // If we've crossed a fullness group,      // move the superblock.      int fullness = sb->getFullness();      if (fullness != oldFullness) {	// Move the superblock.	moveSuperblock (sb, sizeclass, oldFullness, fullness);      }    }  }  // Either we didn't find a superblock or we did and got a block.  assert ((sb == NULL) || (b != NULL));  // Either we didn't get a block or we did and we also got a superblock.  assert ((b == NULL) || (sb != NULL));  return sb;}int hoardHeap::sizeClass (const size_t sz) {  // Find the size class for a given object size  // (the smallest i such that _sizeTable[i] >= sz).  int sizeclass = 0;  while (_sizeTable[sizeclass] < sz)    {      sizeclass++;      assert (sizeclass < SIZE_CLASSES);    }  return sizeclass;}size_t hoardHeap::sizeFromClass (const int sizeclass) {  assert (sizeclass >= 0);  assert (sizeclass < SIZE_CLASSES);  return _sizeTable[sizeclass];}int hoardHeap::getReleaseThreshold (const int sizeclass) {  assert (sizeclass >= 0);  assert (sizeclass < SIZE_CLASSES);  return _threshold[sizeclass];}int hoardHeap::numBlocks (const int sizeclass) {  assert (sizeclass >= 0);  assert (sizeclass < SIZE_CLASSES);  const size_t s = sizeFromClass (sizeclass);  assert (s > 0);  const int blksize = align (sizeof(block) + s);  // Compute the number of blocks that will go into this superblock.  int nb = MAX (1, ((SUPERBLOCK_SIZE - sizeof(superblock)) / blksize));  return nb;}void hoardHeap::lock (void){  assert (_magic == HEAP_MAGIC);  hoardLock (_lock);}void hoardHeap::unlock (void) {  assert (_magic == HEAP_MAGIC);  hoardUnlock (_lock);}size_t hoardHeap::align (const size_t sz){  // Align sz up to the nearest multiple of ALIGNMENT.  // This is much faster than using multiplication  // and division.  return (sz + ALIGNMENT_MASK) & ~ALIGNMENT_MASK;}void hoardHeap::setIndex (int i){  _index = i;}int hoardHeap::getIndex (void){  return _index;}void hoardHeap::recycle (superblock * sb){  assert (sb != NULL);  assert (sb->getOwner() == this);  assert (sb->getNumBlocks() > 1);  assert (sb->getNext() == NULL);  assert (sb->getPrev() == NULL);  assert (hoardHeap::numBlocks(sb->getBlockSizeClass()) > 1);  sb->insertBefore (_reusableSuperblocks);  _reusableSuperblocks = sb;  ++_reusableSuperblocksCount;  // printf ("count: %d => %d\n", getIndex(), _reusableSuperblocksCount);}superblock * hoardHeap::reuse (int sizeclass){  if (_reusableSuperblocks == NULL) {    return NULL;  }  // Make sure that we aren't using a sizeclass  // that is too big for a 'normal' superblock.  if (hoardHeap::numBlocks(sizeclass) <= 1) {    return NULL;  }  // Pop off a superblock from the reusable-superblock list.  assert (_reusableSuperblocksCount > 0);  superblock * sb = _reusableSuperblocks;  _reusableSuperblocks = sb->getNext();  sb->remove();  assert (sb->getNumBlocks() > 1);  --_reusableSuperblocksCount;  // Reformat the superblock if necessary.  if (sb->getBlockSizeClass() != sizeclass) {    decStats (sb->getBlockSizeClass(),	      sb->getNumBlocks() - sb->getNumAvailable(),	      sb->getNumBlocks());    sb = new ((char *) sb) superblock (numBlocks(sizeclass), sizeclass, this);    incStats (sizeclass,	      sb->getNumBlocks() - sb->getNumAvailable(),	      sb->getNumBlocks());  }  assert (sb->getOwner() == this);  assert (sb->getBlockSizeClass() == sizeclass);  return sb;}#endif // _HEAP_H_