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

using namespace BPrivate;

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


int hoardHeap::fMaxThreadHeaps = 1;
int hoardHeap::_numProcessors;
int hoardHeap::_numProcessorsMask;


// 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;
}


//	#pragma mark -


hoardHeap::hoardHeap(void)
	:
	_index(0), _reusableSuperblocks(NULL), _reusableSuperblocksCount(0)
#if HEAP_DEBUG
	, _magic(HEAP_MAGIC)
#endif
{
	initLock();

	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;
}


void
hoardHeap::initNumProcs(void)
{
	system_info info;
	if (get_system_info(&info) != B_OK)
		hoardHeap::_numProcessors = 1;
	else
		hoardHeap::_numProcessors = info.cpu_count;

	fMaxThreadHeaps = 1 << (lg(_numProcessors) + 1);
	_numProcessorsMask = fMaxThreadHeaps - 1;
}