usermode/library/malloc-original/src/hoardheap.cpp

//
// The Hoard Multiprocessor Memory Allocator
// www.hoard.org
//
// Author: Emery Berger, http://www.cs.utexas.edu/users/emery
//
// Copyright (c) 1998-2001, 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 "hoardheap.h"
#include "processheap.h"
#include "superblock.h"

static const char version[] = "The Hoard memory allocator, version 2.1.0 (http://www.hoard.org). Copyright (C) 1998 - 2001 The University of Texas at Austin. $Id: hoardheap.cpp,v 1.84 2001/12/18 02:42:55 emery Exp $";

size_t hoardHeap::_sizeTable[hoardHeap::SIZE_CLASSES]
= {8UL, 16UL, 24UL, 32UL, 40UL, 48UL, 56UL, 64UL, 72UL, 80UL, 88UL, 96UL, 104UL, 112UL, 120UL, 128UL, 136UL, 144UL, 152UL, 160UL, 168UL, 176UL, 184UL, 192UL, 200UL, 208UL, 216UL, 224UL, 232UL, 240UL, 248UL, 256UL, 264UL, 272UL, 280UL, 288UL, 296UL, 304UL, 312UL, 320UL, 328UL, 336UL, 344UL, 352UL, 360UL, 368UL, 376UL, 384UL, 392UL, 400UL, 408UL, 416UL, 424UL, 432UL, 440UL, 448UL, 456UL, 464UL, 472UL, 480UL, 488UL, 496UL, 504UL, 512UL, 576UL, 640UL, 704UL, 768UL, 832UL, 896UL, 960UL, 1024UL, 1088UL, 1152UL, 1216UL, 1280UL, 1344UL, 1408UL, 1472UL, 1536UL, 1600UL, 1664UL, 1728UL, 1792UL, 1856UL, 1920UL, 1984UL, 2048UL, 2112UL, 2560UL, 3072UL, 3584UL, 4096UL, 4608UL, 5120UL, 5632UL, 6144UL, 6656UL, 7168UL, 7680UL, 8192UL, 8704UL, 9216UL, 9728UL, 10240UL, 10752UL, 12288UL, 16384UL, 20480UL, 24576UL, 28672UL, 32768UL, 36864UL, 40960UL, 65536UL, 98304UL, 131072UL, 163840UL, 262144UL, 524288UL, 1048576UL, 2097152UL, 4194304UL, 8388608UL, 16777216UL, 33554432UL, 67108864UL, 134217728UL, 268435456UL, 536870912UL, 1073741824UL, 2147483648UL};

size_t hoardHeap::_threshold[hoardHeap::SIZE_CLASSES]
= {2048UL, 1024UL, 682UL, 512UL, 409UL, 341UL, 292UL, 256UL, 227UL, 204UL, 186UL, 170UL, 157UL, 146UL, 136UL, 128UL, 120UL, 113UL, 107UL, 102UL, 97UL, 93UL, 89UL, 85UL, 81UL, 78UL, 75UL, 73UL, 70UL, 68UL, 66UL, 64UL, 62UL, 60UL, 58UL, 56UL, 55UL, 53UL, 52UL, 51UL, 49UL, 48UL, 47UL, 46UL, 45UL, 44UL, 43UL, 42UL, 41UL, 40UL, 40UL, 39UL, 38UL, 37UL, 37UL, 36UL, 35UL, 35UL, 34UL, 34UL, 33UL, 33UL, 32UL, 32UL, 28UL, 25UL, 23UL, 21UL, 19UL, 18UL, 17UL, 16UL, 15UL, 14UL, 13UL, 12UL, 12UL, 11UL, 11UL, 10UL, 10UL, 9UL, 9UL, 9UL, 8UL, 8UL, 8UL, 8UL, 7UL, 6UL, 5UL, 4UL, 4UL, 3UL, 3UL, 2UL, 2UL, 2UL, 2UL, 2UL, 2UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL, 1UL};


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())) {
    // This superblock is empty --
    // recycle this superblock (make it available for any sizeclass).
    recycle (sb);

  } 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,
              0,
              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);
#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
    sb->superblock::~superblock();
    hoardFreeMemory (sb);
    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
  // or free it.

  if ((newFullness == 0) &&
      (sb->getNumBlocks() == sb->getNumAvailable())) {

    removeSuperblock (sb, sizeclass);
    if (_numProcessors == 1) {
      hoardFreeMemory (sb);
    } else {
      recycle (sb);
      // Update the stats.  This restores the stats to their state
      // before the call to removeSuperblock, above.
      incStats (sizeclass, 0, sb->getNumBlocks());
    }
  }

  // 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);
    const bool crossedThreshold 
      = ((inUse < allocated - getReleaseThreshold(sizeclass)) && 
         (EMPTY_FRACTION * inUse < EMPTY_FRACTION * allocated - allocated));
    if (crossedThreshold) {
      
        // 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;
}

// 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()) + 4)) - 1;
  if (hoardHeap::_numProcessors > MAX_HEAPS) {
          hoardHeap::_numProcessorsMask = MAX_HEAPS_MASK;
  }
}

static hoardHeap::_initNumProcs initProcs;

---