heap.h

newos is new operation system

///-*-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 declaration


class 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_STATS
int 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();
}
#endif


superblock * 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_