heap.cpp

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.
//
//////////////////////////////////////////////////////////////////////////////
#include "config.h"

#include "heap.h"
#include "processheap.h"
#include "superblock.h"

static const char version[] = "The Hoard memory allocator, version 2.0 (http://www.hoard.org). Copyright (C) 1998, 1999, 2000 The University of Texas at Austin. $Id: heap.cpp,v 1.74 2001/03/22 22:10:35 emery Exp $";

// NB: Use maketable.cpp to update this
//     if SIZE_CLASSES, ALIGNMENT, SIZE_CLASS_BASE, MAX_EMPTY_SUPERBLOCKS,
//     or SUPERBLOCK_SIZE changes.

#if (MAX_INTERNAL_FRAGMENTATION == 2)

size_t hoardHeap::_sizeTable[hoardHeap::SIZE_CLASSES] = {8UL, 16UL, 24UL, 32UL, 40UL, 48UL, 56UL, 72UL, 80UL, 96UL, 120UL, 144UL, 168UL, 200UL, 240UL, 288UL, 344UL, 416UL, 496UL, 592UL, 712UL, 856UL, 1024UL, 1232UL, 1472UL, 1768UL, 2120UL, 2544UL, 3048UL, 3664UL, 4392UL, 5272UL, 6320UL, 7584UL, 9104UL, 10928UL, 13112UL, 15728UL, 18872UL, 22648UL, 27176UL, 32616UL, 39136UL, 46960UL, 56352UL, 67624UL, 81144UL, 97376UL, 116848UL, 140216UL, 168256UL, 201904UL, 242288UL, 290744UL, 348896UL, 418672UL, 502408UL, 602888UL, 723464UL, 868152UL, 1041784UL, 1250136UL, 1500160UL, 1800192UL, 2160232UL, 2592280UL, 3110736UL, 3732880UL, 4479456UL, 5375344UL, 6450408UL, 7740496UL, 9288592UL, 11146312UL, 13375568UL, 16050680UL, 19260816UL, 23112984UL, 27735576UL, 33282688UL, 39939224UL, 47927072UL, 57512488UL, 69014984UL, 82817976UL, 99381576UL, 119257888UL, 143109472UL, 171731360UL, 206077632UL, 247293152UL, 296751776UL, 356102144UL, 427322560UL, 512787072UL, 615344512UL, 738413376UL, 886096064UL, 1063315264UL}; 

size_t hoardHeap::_threshold[hoardHeap::SIZE_CLASSES] = {4096UL, 2048UL, 1364UL, 1024UL, 816UL, 680UL, 584UL, 452UL, 408UL, 340UL, 272UL, 224UL, 192UL, 160UL, 136UL, 112UL, 92UL, 76UL, 64UL, 52UL, 44UL, 36UL, 32UL, 24UL, 20UL, 16UL, 12UL, 12UL, 8UL, 8UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL}; 

#elif (MAX_INTERNAL_FRAGMENTATION == 6)

size_t hoardHeap::_sizeTable[hoardHeap::SIZE_CLASSES] = {8UL, 16UL, 24UL, 32UL, 48UL, 72UL, 112UL, 176UL, 288UL, 456UL, 728UL, 1160UL, 1848UL, 2952UL, 4728UL, 7560UL, 12096UL, 19344UL, 30952UL, 49520UL, 79232UL, 126768UL, 202832UL, 324520UL, 519232UL, 830768UL, 1329232UL, 2126768UL, 3402824UL, 5444520UL, 8711232UL, 13937968UL, 22300752UL, 35681200UL, 57089912UL, 91343856UL, 146150176UL, 233840256UL, 374144416UL, 598631040UL, 957809728UL, 1532495488UL}; 

size_t hoardHeap::_threshold[hoardHeap::SIZE_CLASSES] = {4096UL, 2048UL, 1364UL, 1024UL, 680UL, 452UL, 292UL, 184UL, 112UL, 68UL, 44UL, 28UL, 16UL, 8UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL}; 

#elif (MAX_INTERNAL_FRAGMENTATION == 10)

size_t hoardHeap::_sizeTable[hoardHeap::SIZE_CLASSES] = {8UL, 16UL, 32UL, 64UL, 128UL, 256UL, 512UL, 1024UL, 2048UL, 4096UL, 8192UL, 16384UL, 32768UL, 65536UL, 131072UL, 262144UL, 524288UL, 1048576UL, 2097152UL, 4194304UL, 8388608UL, 16777216UL, 33554432UL, 67108864UL, 134217728UL, 268435456UL, 536870912UL, 1073741824UL, 2147483648UL}; 

size_t hoardHeap::_threshold[hoardHeap::SIZE_CLASSES] = {4096UL, 2048UL, 1024UL, 512UL, 256UL, 128UL, 64UL, 32UL, 16UL, 8UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL}; 

#else
#error "Undefined size class base."
#endif


hoardHeap::hoardHeap (void)
  : _index (0),
    _reusableSuperblocks (NULL),
    _reusableSuperblocksCount (0)
#if HEAP_DEBUG
  , _magic (HEAP_MAGIC)
#endif
{
  // Initialize the per-heap lock.
  hoardLockInit (_lock);
  for (int i = 0; i < SUPERBLOCK_FULLNESS_GROUP; i++) {
    for (int j = 0; j < SIZE_CLASSES; j++) {
      // Initialize all superblocks lists to empty.
      _superblocks[i][j] = NULL;
    }
  }
  for (int k = 0; k < SIZE_CLASSES; k++) {
    _leastEmptyBin[k] = 0;
  }
}


void hoardHeap::insertSuperblock (int sizeclass,
				  superblock * sb,
				  processHeap * pHeap)
{
  assert (sb->isValid());
  assert (sb->getBlockSizeClass() == sizeclass);
  assert (sb->getPrev() == NULL);
  assert (sb->getNext() == NULL);
  assert (_magic == HEAP_MAGIC);

  // Now it's ours.
  sb->setOwner (this);

  // How full is this superblock?  We'll use this information to put
  // it into the right 'bin'.
  sb->computeFullness();
  int fullness = sb->getFullness();

  // Update the stats.
  incStats (sizeclass,
	    sb->getNumBlocks() - sb->getNumAvailable(),
	    sb->getNumBlocks());

  if ((fullness == 0) &&
      (sb->getNumBlocks() > 1) &&
      (sb->getNumBlocks() == sb->getNumAvailable())) {
    // Recycle this superblock.
#if 0
    removeSuperblock (sb, sizeclass);
    // Update the stats.
    decStats (sizeclass,
	      sb->getNumBlocks() - sb->getNumAvailable(),
	      sb->getNumBlocks());
    // Free it immediately.
    const size_t s = sizeFromClass (sizeclass);
    const int blksize = align (sizeof(block) + s);
#if HEAP_LOG
    // Record the memory deallocation.
    MemoryRequest m;
    m.deallocate ((int) sb->getNumBlocks() * (int) sizeFromClass(sb->getBlockSizeClass()));
    pHeap->getLog(getIndex()).append(m);
#endif
#if HEAP_FRAG_STATS
    pHeap->setDeallocated (0, sb->getNumBlocks() * sizeFromClass(sb->getBlockSizeClass()));
#endif
    hoardUnsbrk (sb, align (sizeof(superblock) + blksize));
#else
    recycle (sb);
#endif
  } else {

    // Insert it into the appropriate list.
    superblock *& head = _superblocks[fullness][sizeclass];
    sb->insertBefore (head);
    head = sb;
    assert (head->isValid());
    
    // Reset the least-empty bin counter.
    _leastEmptyBin[sizeclass] = RESET_LEAST_EMPTY_BIN;
  }
}


superblock * hoardHeap::removeMaxSuperblock (int sizeclass)
{
  assert (_magic == HEAP_MAGIC);

  superblock * head = NULL;

  // First check the reusable superblocks list.

  head = reuse (sizeclass);
  if (head) {
    // We found one. Since we're removing this superblock, update the
    // stats accordingly.
    decStats (sizeclass,
	      head->getNumBlocks() - head->getNumAvailable(),
	      head->getNumBlocks());

    return head;
  }

  // Instead of finding the superblock with the most available space
  // (something that would either involve a linear scan through the
  // superblocks or maintaining the superblocks in sorted order), we
  // just pick one that is no more than
  // 1/(SUPERBLOCK_FULLNESS_GROUP-1) more full than the superblock
  // with the most available space.  We start with the emptiest group.

  int i = 0;

  // Note: the last group (SUPERBLOCK_FULLNESS_GROUP - 1) is full, so
  // we never need to check it. But for robustness, we leave it in.
  while (i < SUPERBLOCK_FULLNESS_GROUP) {
    head = _superblocks[i][sizeclass];
    if (head) {
      break;
    }
    i++;
  }

  if (!head) {
    return NULL;
  }

  // Make sure that this superblock is at least 1/EMPTY_FRACTION
  // empty.
  assert (head->getNumAvailable() * EMPTY_FRACTION >= head->getNumBlocks());

  removeSuperblock (head, sizeclass);

  assert (head->isValid());
  assert (head->getPrev() == NULL);
  assert (head->getNext() == NULL);
  return head;
}


void hoardHeap::removeSuperblock (superblock * sb,
				  int sizeclass)
{
  assert (_magic == HEAP_MAGIC);

  assert (sb->isValid());
  assert (sb->getOwner() == this);
  assert (sb->getBlockSizeClass() == sizeclass);

  for (int i = 0; i < SUPERBLOCK_FULLNESS_GROUP; i++) {
    if (sb == _superblocks[i][sizeclass]) {
      _superblocks[i][sizeclass] = sb->getNext();
      if (_superblocks[i][sizeclass] != NULL) {
	assert (_superblocks[i][sizeclass]->isValid());
      }
      break;
    }
  }

  sb->remove();
  decStats (sizeclass, sb->getNumBlocks() - sb->getNumAvailable(), sb->getNumBlocks());
}


void hoardHeap::moveSuperblock (superblock * sb,
				int sizeclass,
				int fromBin,
				int toBin)
{
  assert (_magic == HEAP_MAGIC);
  assert (sb->isValid());
  assert (sb->getOwner() == this);
  assert (sb->getBlockSizeClass() == sizeclass);
  assert (sb->getFullness() == toBin);

  // Remove the superblock from the old bin.

  superblock *& oldHead = _superblocks[fromBin][sizeclass];
  if (sb == oldHead) {
    oldHead = sb->getNext();
    if (oldHead != NULL) {
      assert (oldHead->isValid());
    }
  }

  sb->remove();

  // Insert the superblock into the new bin.

  superblock *& newHead = _superblocks[toBin][sizeclass];
  sb->insertBefore (newHead);
  newHead = sb;
  assert (newHead->isValid());

  // Reset the least-empty bin counter.
  _leastEmptyBin[sizeclass] = RESET_LEAST_EMPTY_BIN;
}


// The heap lock must be held when this procedure is called.

int hoardHeap::freeBlock (block *& b,
			   superblock *& sb,
			   int sizeclass,
			   processHeap * pHeap)
{
  assert (sb->isValid());
  assert (b->isValid());
  assert (this == sb->getOwner());

  const int oldFullness = sb->getFullness();
  sb->putBlock (b);
  decUStats (sizeclass);
  const int newFullness = sb->getFullness();
  
  // Free big superblocks.
  if (sb->getNumBlocks() == 1) {
    removeSuperblock (sb, sizeclass);
    const size_t s = sizeFromClass (sizeclass);
    const int blksize = align (sizeof(block) + s);
#if HEAP_LOG
    // Record the memory deallocation.
    MemoryRequest m;
    m.deallocate ((int) sb->getNumBlocks() * (int) sizeFromClass(sb->getBlockSizeClass()));
    pHeap->getLog(getIndex()).append(m);
#endif
#if HEAP_FRAG_STATS
    pHeap->setDeallocated (0, sb->getNumBlocks() * sizeFromClass(sb->getBlockSizeClass()));
#endif
    hoardUnsbrk (sb, align (sizeof(superblock) + blksize));
    return 1;
  }

  // If the fullness value has changed, move the superblock.
  if (newFullness != oldFullness) {
    moveSuperblock (sb, sizeclass, oldFullness, newFullness);
  } else {
    // Move the superblock to the front of its list (to reduce
    // paging).
    superblock *& head = _superblocks[newFullness][sizeclass];
    if (sb != head) {
      sb->remove();
      sb->insertBefore (head);
      head = sb;
    }
  }
 
  // If the superblock is now empty, recycle it.

  if ((newFullness == 0) &&
      (sb->getNumBlocks() == sb->getNumAvailable())) {
    removeSuperblock (sb, sizeclass);
#if 0
    // Free it immediately.
    const size_t s = sizeFromClass (sizeclass);
    const int blksize = align (sizeof(block) + s);
#if HEAP_LOG
    // Record the memory deallocation.
    MemoryRequest m;
    m.deallocate ((int) sb->getNumBlocks() * (int) sizeFromClass(sb->getBlockSizeClass()));
    pHeap->getLog(getIndex()).append(m);
#endif
#if HEAP_FRAG_STATS
    pHeap->setDeallocated (0, sb->getNumBlocks() * sizeFromClass(sb->getBlockSizeClass()));
#endif
    hoardUnsbrk (sb, align (sizeof(superblock) + blksize));
    return 1;
#else
    recycle (sb);
    // Update the stats.  This restores the stats to their state
    // before the call to removeSuperblock, above.
    incStats (sizeclass,
	      sb->getNumBlocks() - sb->getNumAvailable(),
	      sb->getNumBlocks());
#endif
  }

  // If this is the process heap, then we're done.
  if (this == (hoardHeap *) pHeap) {
    return 0;
  }

  //
  // Release a superblock, if necessary.
  //

  //
  // Check to see if the amount free exceeds the release threshold
  // (two superblocks worth of blocks for a given sizeclass) and if
  // the heap is sufficiently empty.
  //

  // We never move anything to the process heap if we're on a
  // uniprocessor.
  if (_numProcessors > 1) {
    int inUse, allocated;
    getStats (sizeclass, inUse, allocated);
    if ((inUse < allocated - getReleaseThreshold(sizeclass))
	&& (EMPTY_FRACTION * inUse < EMPTY_FRACTION * allocated - allocated)) {
      
      // We've crossed the magical threshold. Find the superblock with
      // the most free blocks and give it to the process heap.
      superblock * const maxSb = removeMaxSuperblock (sizeclass);
      assert (maxSb != NULL);
      
      // Update the statistics.
      
      assert (maxSb->getNumBlocks() >= maxSb->getNumAvailable());
      
      // Give the superblock back to the process heap.
      pHeap->release (maxSb);
      
    }
  }

  return 0;
}

// Return ceil(log_2(num)).
// num must be positive.
static int lg (int num)
{
  assert (num > 0);
  int power = 0;
  int n = 1;
  // Invariant: 2^power == n.
  while (n < num) {
    n <<= 1;
    power++;
  }
  return power;
}

// Static initialization of the number of processors (and a mask).
   
int hoardHeap::_numProcessors;
int hoardHeap::_numProcessorsMask;

hoardHeap::_initNumProcs::_initNumProcs(void)
{
  hoardHeap::_numProcessors = hoardGetNumProcessors();
  hoardHeap::_numProcessorsMask = (1 << (lg(hoardGetNumProcessors()) + 1)) - 1;
}

static hoardHeap::_initNumProcs initProcs;