/*
 * Copyright 2006, Haiku Inc.
 * Copyright 2002, Thomas Kurschel.
 *
 * Distributed under the terms of the MIT license.
 */

/**	Memory manager used for graphics mem
 *
 *	It has the following features
 *	- doesn't access memory to be managed
 *	- memory block's owner is identified by tag,
 *	  tag is verified during free, and all memory
 *	  belonging to one tag can be freed at once
 *	- multi-threading save
 */

#include "memory_manager.h"

#include <KernelExport.h>
#include <stdlib.h>


//#define TRACE_MEMORY_MANAGER
#ifdef TRACE_MEMORY_MANAGER
#	define TRACE(x) dprintf x
#else
#	define TRACE(x) ;
#endif


// allocated memory block
typedef struct mem_block {
	struct mem_block *prev, *next;
	uint32 base;
	uint32 size;
	void *tag;
	bool allocated;
} mem_block;

// memory heap
struct mem_info {
	mem_block *first;
	area_id heap_area;
	uint32 block_size;
	sem_id lock;
	mem_block *heap;
	mem_block *unused;
	uint32 heap_entries;
};


/** merge "block" with successor */

static void
merge(mem_info *mem, mem_block *block)
{
	mem_block *next = block->next;

	block->size += next->size;

	if (next->next)
		next->next->prev = block;

	block->next = next->next;
	next->next = mem->unused;
	mem->unused = next;
}


/** free memory block including merge */

static mem_block *
freeblock(mem_info *mem, mem_block *block)
{
	mem_block *prev, *next;

	block->allocated = false;
	prev = block->prev;

	if (prev && !prev->allocated) {
		block = prev;
		merge(mem, prev);
	}

	next = block->next;

	if (next && !next->allocated)
		merge(mem, block);

	return block;
}


//	#pragma mark -


/** Init memory manager.
 *
 *	\param start start of address space
 *	\param length length of address space
 *	\param blockSize - granularity
 *	\param heapEntries - maximum number of blocks
 */

mem_info *
mem_init(const char* name, uint32 start, uint32 length,
	uint32 blockSize, uint32 heapEntries)
{
	mem_block *first;
	mem_info *mem;
	uint i;
	uint32 size;

	TRACE(("mem_init(name=%s, start=%lx, length=%lx, blockSize=%lx, heapEntries=%ld)\n",
		name, start, length, blockSize, heapEntries));

	mem = malloc(sizeof(*mem));
	if (mem == NULL)
		goto err1;

	mem->block_size = blockSize;
	mem->heap_entries = heapEntries;
	mem->lock = create_sem(1, name);
	if (mem->lock < 0)
		goto err2;

	// align size to B_PAGE_SIZE
	size = heapEntries * sizeof(mem_block);
	size = (size + B_PAGE_SIZE - 1) & ~(B_PAGE_SIZE - 1);

	mem->heap_area = create_area(name, (void **)&mem->heap,
		B_ANY_ADDRESS, size, B_FULL_LOCK, B_READ_AREA | B_WRITE_AREA);

	if (mem->heap_area < 0 || mem->heap == NULL)
		goto err3;

	for (i = 1; i < heapEntries; ++i) {
		mem->heap[i - 1].next = &mem->heap[i];
	}

	mem->heap[heapEntries - 1].next = NULL;
	mem->unused = &mem->heap[1];

	first = &mem->heap[0];
	mem->first = first;

	first->base = start;
	first->size = length;
	first->prev = first->next = NULL;
	first->allocated = false;
	
	return mem;

err3:
	delete_sem(mem->lock);
err2:
	free(mem);
err1:
	return NULL;
}


/** destroy heap */

void
mem_destroy(mem_info *mem)
{
	TRACE(("mem_destroy(mem %p)\n", mem));

	delete_area(mem->heap_area);
	delete_sem(mem->lock);
	free(mem);
}


/** Allocate memory block
 *
 *	\param mem heap handle
 *	\param size size in bytes
 *	\param tag owner tag
 *
 *	\param blockID - returns block id
 *	\param offset - returns start address of block
 */

status_t
mem_alloc(mem_info *mem, uint32 size, void *tag, uint32 *blockID, uint32 *offset)
{
	mem_block *current, *newEntry;
	status_t status;

	TRACE(("mem_alloc(mem %p, size=%lx, tag=%p)\n", mem, size, tag));

	status = acquire_sem(mem->lock);
	if (status != B_OK)
		return status;

	// we assume block_size is power of two	
	size = (size + mem->block_size - 1) & ~(mem->block_size - 1);

	// simple first fit	
	for (current = mem->first; current; current = current->next) {
		if (!current->allocated && current->size >= size)
			break;
	}

	if (current == NULL) {
		TRACE(("mem_alloc: out of memory\n"));
		goto err;
	}

	if (size != current->size) {
		newEntry = mem->unused;

		if (newEntry == NULL) {
			TRACE(("mem_alloc: out of blocks\n"));
			goto err;
		}

		mem->unused = newEntry->next;

		newEntry->next = current->next;
		newEntry->prev = current;	
		newEntry->allocated = false;
		newEntry->base = current->base + size;
		newEntry->size = current->size - size;

		if (current->next)
			current->next->prev = newEntry;

		current->next = newEntry;
		current->size = size;
	}

	current->allocated = true;
	current->tag = tag;

	*blockID = current - mem->heap + 1;
	*offset = current->base;

	release_sem(mem->lock);

	TRACE(("mem_alloc(block_id=%ld, offset=%lx)\n", *blockID, *offset));
	return B_OK;

err:
	release_sem(mem->lock);
	return B_NO_MEMORY;
}


/** Free memory
 *	\param mem heap handle
 *	\param blockID block id
 *	\param tag owner tag (must match tag passed to mem_alloc())
 */

status_t
mem_free(mem_info *mem, uint32 blockID, void *tag)
{	
	mem_block *block;
	status_t status;

	TRACE(("mem_free(mem %p, blockID=%ld, tag=%p)\n", mem, blockID, tag));

	status = acquire_sem(mem->lock);
	if (status != B_OK)
		return status;

	--blockID;

	if (blockID >= mem->heap_entries) {
		TRACE(("mem_free: invalid ID %lu\n", blockID));
		goto err;
	}

	block = &mem->heap[blockID];
	if (!block->allocated || block->tag != tag) {
		TRACE(("mem_free: not owner\n"));
		goto err;
	}

	freeblock(mem, block);

	release_sem(mem->lock);
	return B_OK;

err:
	release_sem(mem->lock);
	return B_BAD_VALUE;
}


/** Free all memory belonging to owner "tag" */

status_t
mem_freetag(mem_info *mem, void *tag)
{
	mem_block *current;
	status_t status;

	TRACE(("mem_freetag(mem %p, tag=%p)\n", mem, tag));

	status = acquire_sem(mem->lock);
	if (status != B_OK)
		return status;
	
	for (current = mem->first; current; current = current->next) {
		if (current->allocated && current->tag == tag)
			current = freeblock(mem, current);
	}

	release_sem(mem->lock);
	return B_OK;
}