haiku.git

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

/*
  superblock.h
  ------------------------------------------------------------------------
  The superblock class controls a number of blocks (which are
  allocatable units of memory).
  ------------------------------------------------------------------------
  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 _SUPERBLOCK_H_
#define _SUPERBLOCK_H_

#include "config.h"
#include "arch-specific.h"
#include "block.h"


namespace BPrivate {

class hoardHeap;				// forward declaration
class processHeap;				// forward declaration

class superblock {
	public:
		// Construct a superblock for a given size class and set the heap
		// owner.
		superblock(int numblocks, int sizeclass, hoardHeap *owner);
		~superblock(void) {}

		// Make (allocate or re-use) a superblock for a given size class.
		static superblock *makeSuperblock(int sizeclass, processHeap *pHeap);

		// Find out who allocated this superblock.
		inline hoardHeap *getOwner(void);

		// Set the superblock's owner.
		inline void setOwner(hoardHeap *o);

		// Get a block from the superblock.
		inline block *getBlock(void);

		// Put a block back in the superblock.
		inline void putBlock(block *b);

		// How many blocks are available?
		inline int getNumAvailable(void);

		// How many blocks are there, in total?
		inline int getNumBlocks(void);

		// What size class are blocks in this superblock?
		inline int getBlockSizeClass(void);

		// Insert this superblock before the next one.
		inline void insertBefore(superblock *nextSb);

		// Return the next pointer (to the next superblock in the list).
		inline superblock *const getNext(void);

		// Return the prev pointer (to the previous superblock in the list).
		inline superblock *const getPrev(void);

		// Compute the 'fullness' of this superblock.
		inline void computeFullness(void);

		// Return the 'fullness' of this superblock.
		inline int getFullness(void);

#if HEAP_FRAG_STATS
		// Return the amount of waste in every allocated block.
		int getMaxInternalFragmentation(void);
#endif

		// Remove this superblock from its linked list.
		inline void remove(void);

		// Is this superblock valid? (i.e.,
		// does it have the right magic number?)
		inline int isValid(void);

		void
		upLock(void)
		{
			hoardLock(_upLock);
		}

		void
		upUnlock(void)
		{
			hoardUnlock(_upLock);
		}

	private:
		// Disable copying and assignment.

		superblock(const superblock &);
		const superblock & operator=(const superblock &);

		// Used for sanity checking.
		enum { SUPERBLOCK_MAGIC = 0xCAFEBABE };

#if HEAP_DEBUG
		unsigned long _magic;
#endif

		const int _sizeClass;		// The size class of blocks in the superblock.
		const int _numBlocks;		// The number of blocks in the superblock.
		int _numAvailable;			// The number of blocks available.
		int _fullness;				// How full is this superblock?
		// (which SUPERBLOCK_FULLNESS group is it in)
		block *_freeList;			// A pointer to the first free block.
		hoardHeap *_owner;			// The heap who owns this superblock.
		superblock *_next;			// The next superblock in the list.
		superblock *_prev;			// The previous superblock in the list.

		hoardLockType _upLock;		// Lock this when moving a superblock to the global (process) heap.

		// We insert a cache pad here to prevent false sharing with the
		// first block (which immediately follows the superblock).
		double _pad[CACHE_LINE / sizeof(double)];
};


hoardHeap *
superblock::getOwner(void)
{
	assert(isValid());
	hoardHeap *o = _owner;
	return o;
}


void
superblock::setOwner(hoardHeap *o)
{
	assert(isValid());
	_owner = o;
}


block *
superblock::getBlock(void)
{
	assert(isValid());
	// Pop off a block from this superblock's freelist,
	// if there is one available.
	if (_freeList == NULL) {
		// The freelist is empty.
		assert(getNumAvailable() == 0);
		return NULL;
	}

	assert(getNumAvailable() > 0);
	block *b = _freeList;
	_freeList = _freeList->getNext();
	_numAvailable--;

	b->setNext(NULL);

	computeFullness();
	return b;
}


void
superblock::putBlock(block *b)
{
	assert(isValid());
	// Push a block onto the superblock's freelist.
	assert(b->isValid());
	assert(b->getSuperblock() == this);
	assert(getNumAvailable() < getNumBlocks());
	b->setNext(_freeList);
	_freeList = b;
	_numAvailable++;
	computeFullness();
}


int
superblock::getNumAvailable(void)
{
	assert(isValid());
	return _numAvailable;
}


int
superblock::getNumBlocks(void)
{
	assert(isValid());
	return _numBlocks;
}


int
superblock::getBlockSizeClass(void)
{
	assert(isValid());
	return _sizeClass;
}


superblock * const
superblock::getNext(void)
{
	assert(isValid());
	return _next;
}

superblock * const
superblock::getPrev(void)
{
	assert(isValid());
	return _prev;
}


void
superblock::insertBefore(superblock * nextSb)
{
	assert(isValid());
	// Insert this superblock before the next one (nextSb).
	assert(nextSb != this);
	_next = nextSb;
	if (nextSb) {
		_prev = nextSb->_prev;
		nextSb->_prev = this;
	}
}


void
superblock::remove(void)
{
	// Remove this superblock from a doubly-linked list.
	if (_next)
		_next->_prev = _prev;
	if (_prev)
		_prev->_next = _next;

	_prev = NULL;
	_next = NULL;
}


int
superblock::isValid(void)
{
	assert(_numBlocks > 0);
	assert(_numAvailable <= _numBlocks);
	assert(_sizeClass >= 0);
	return 1;
}


void
superblock::computeFullness(void)
{
	assert(isValid());
	_fullness = (((SUPERBLOCK_FULLNESS_GROUP - 1)
		* (getNumBlocks() - getNumAvailable())) / getNumBlocks());
}


int
superblock::getFullness(void)
{
	assert(isValid());
	return _fullness;
}

}	// namespace BPrivate

#endif // _SUPERBLOCK_H_