/*
 * Copyright (c) 2009 Martin Decky
 * Copyright (c) 2009 Tomas Bures
 * Copyright (c) 2009 Lubomir Bulej
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <malloc.h>
#include <as.h>
#include <adt/list.h>
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include "../tester.h"
#include "common.h"

/*
 * Global error flag. The flag is set if an error
 * is encountered (overlapping blocks, inconsistent
 * block data, etc.)
 */
bool error_flag = false;

/*
 * Memory accounting: the amount of allocated memory and the
 * number and list of allocated blocks.
 */
size_t mem_allocated;
size_t mem_blocks_count;

static LIST_INITIALIZE(mem_blocks);
static LIST_INITIALIZE(mem_areas);

/** Initializes the memory accounting structures.
 *
 */
void init_mem(void)
{
	mem_allocated = 0;
	mem_blocks_count = 0;
}

/** Cleanup all allocated memory blocks and mapped areas.
 *
 * Set the global error_flag if an error occurs.
 *
 */
void done_mem(void)
{
	link_t *link;
	
	while ((link = list_first(&mem_blocks)) != NULL) {
		mem_block_t *block = list_get_instance(link, mem_block_t, link);
		free_block(block);
	}
	
	while ((link = list_first(&mem_areas)) != NULL) {
		mem_area_t *area = list_get_instance(link, mem_area_t, link);
		unmap_area(area);
	}
}

static bool overlap_match(mem_block_t *block, void *addr, size_t size)
{
	/* Entry block control structure <mbeg, mend) */
	uint8_t *mbeg = (uint8_t *) block;
	uint8_t *mend = (uint8_t *) block + sizeof(mem_block_t);
	
	/* Entry block memory <bbeg, bend) */
	uint8_t *bbeg = (uint8_t *) block->addr;
	uint8_t *bend = (uint8_t *) block->addr + block->size;
	
	/* Data block <dbeg, dend) */
	uint8_t *dbeg = (uint8_t *) addr;
	uint8_t *dend = (uint8_t *) addr + size;
	
	/* Check for overlaps */
	if (((mbeg >= dbeg) && (mbeg < dend)) ||
	    ((mend > dbeg) && (mend <= dend)) ||
	    ((bbeg >= dbeg) && (bbeg < dend)) ||
	    ((bend > dbeg) && (bend <= dend)))
		return true;
	
	return false;
}

/** Test overlap
 *
 * Test whether a block starting at @addr overlaps with another,
 * previously allocated memory block or its control structure.
 *
 * @param addr Initial address of the block
 * @param size Size of the block
 *
 * @return False if the block does not overlap.
 *
 */
static int test_overlap(void *addr, size_t size)
{
	bool fnd = false;
	
	list_foreach(mem_blocks, link, mem_block_t, block) {
		if (overlap_match(block, addr, size)) {
			fnd = true;
			break;
		}
	}
	
	return fnd;
}

static void check_consistency(const char *loc)
{
	/* Check heap consistency */
	void *prob = heap_check();
	if (prob != NULL) {
		TPRINTF("\nError: Heap inconsistency at %p in %s.\n",
		    prob, loc);
		TSTACKTRACE();
		error_flag = true;
	}
}

/** Checked malloc
 *
 * Allocate @size bytes of memory and check whether the chunk comes
 * from the non-mapped memory region and whether the chunk overlaps
 * with other, previously allocated, chunks.
 *
 * @param size Amount of memory to allocate
 *
 * @return NULL if the allocation failed. Sets the global error_flag to
 *         true if the allocation succeeded but is illegal.
 *
 */
static void *checked_malloc(size_t size)
{
	void *data;
	
	/* Allocate the chunk of memory */
	data = malloc(size);
	check_consistency("checked_malloc");
	if (data == NULL)
		return NULL;
	
	/* Check for overlaps with other chunks */
	if (test_overlap(data, size)) {
		TPRINTF("\nError: Allocated block overlaps with another "
		    "previously allocated block.\n");
		TSTACKTRACE();
		error_flag = true;
	}
	
	return data;
}


/* Allocate block
 *
 * Allocate a block of memory of @size bytes and add record about it into
 * the mem_blocks list. Return a pointer to the block holder structure or
 * NULL if the allocation failed.
 *
 * If the allocation is illegal (e.g. the memory does not come from the
 * right region or some of the allocated blocks overlap with others),
 * set the global error_flag.
 *
 * @param size Size of the memory block
 *
 */
mem_block_t *alloc_block(size_t size)
{
	/* Check for allocation limit */
	if (mem_allocated >= MAX_ALLOC)
		return NULL;
	
	/* Allocate the block holder */
	mem_block_t *block =
	    (mem_block_t *) checked_malloc(sizeof(mem_block_t));
	if (block == NULL)
		return NULL;
	
	link_initialize(&block->link);
	
	/* Allocate the block memory */
	block->addr = checked_malloc(size);
	if (block->addr == NULL) {
		free(block);
		check_consistency("alloc_block");
		return NULL;
	}
	
	block->size = size;
	
	/* Register the allocated block */
	list_append(&block->link, &mem_blocks);
	mem_allocated += size + sizeof(mem_block_t);
	mem_blocks_count++;
	
	return block;
}

/** Free block
 *
 * Free the block of memory and the block control structure allocated by
 * alloc_block. Set the global error_flag if an error occurs.
 *
 * @param block Block control structure
 *
 */
void free_block(mem_block_t *block)
{
	/* Unregister the block */
	list_remove(&block->link);
	mem_allocated -= block->size + sizeof(mem_block_t);
	mem_blocks_count--;
	
	/* Free the memory */
	free(block->addr);
	check_consistency("free_block (a)");
	free(block);
	check_consistency("free_block (b)");
}

/** Calculate expected value
 *
 * Compute the expected value of a byte located at @pos in memory
 * block described by @block.
 *
 * @param block Memory block control structure
 * @param pos   Position in the memory block data area
 *
 */
static inline uint8_t block_expected_value(mem_block_t *block, uint8_t *pos)
{
	return ((uintptr_t) block ^ (uintptr_t) pos) & 0xff;
}

/** Fill block
 *
 * Fill the memory block controlled by @block with data.
 *
 * @param block Memory block control structure
 *
 */
void fill_block(mem_block_t *block)
{
	for (uint8_t *pos = block->addr, *end = pos + block->size;
	    pos < end; pos++)
		*pos = block_expected_value(block, pos);
	
	check_consistency("fill_block");
}

/** Check block
 *
 * Check whether the block @block contains the data it was filled with.
 * Set global error_flag if an error occurs.
 *
 * @param block Memory block control structure
 *
 */
void check_block(mem_block_t *block)
{
	for (uint8_t *pos = block->addr, *end = pos + block->size;
	    pos < end; pos++) {
		if (*pos != block_expected_value(block, pos)) {
			TPRINTF("\nError: Corrupted content of a data block.\n");
			TSTACKTRACE();
			error_flag = true;
			return;
		}
	}
}

/** Get random block
 *
 * Select a random memory block from the list of allocated blocks.
 *
 * @return Block control structure or NULL if the list is empty.
 *
 */
mem_block_t *get_random_block(void)
{
	if (mem_blocks_count == 0)
		return NULL;
	
	unsigned long idx = rand() % mem_blocks_count;
	link_t *entry = list_nth(&mem_blocks, idx);
	
	if (entry == NULL) {
		TPRINTF("\nError: Corrupted list of allocated memory blocks.\n");
		TSTACKTRACE();
		error_flag = true;
	}
	
	return list_get_instance(entry, mem_block_t, link);
}

/* Map memory area
 *
 * Map a memory area of @size bytes and add record about it into
 * the mem_areas list. Return a pointer to the area holder structure or
 * NULL if the mapping failed.
 *
 * @param size Size of the memory area
 *
 */
mem_area_t *map_area(size_t size)
{
	/* Allocate the area holder */
	mem_area_t *area =
	    (mem_area_t *) checked_malloc(sizeof(mem_area_t));
	if (area == NULL)
		return NULL;
	
	link_initialize(&area->link);
	
	area->addr = as_area_create(AS_AREA_ANY, size,
	    AS_AREA_WRITE | AS_AREA_READ | AS_AREA_CACHEABLE,
	    AS_AREA_UNPAGED);
	if (area->addr == AS_MAP_FAILED) {
		free(area);
		check_consistency("map_area (a)");
		return NULL;
	}
	
	area->size = size;
	
	/* Register the allocated area */
	list_append(&area->link, &mem_areas);
	
	return area;
}

/** Unmap area
 *
 * Unmap the memory area and free the block control structure.
 * Set the global error_flag if an error occurs.
 *
 * @param area Memory area control structure
 *
 */
void unmap_area(mem_area_t *area)
{
	/* Unregister the area */
	list_remove(&area->link);
	
	/* Free the memory */
	int ret = as_area_destroy(area->addr);
	if (ret != EOK)
		error_flag = true;
	
	free(area);
	check_consistency("unmap_area");
}

/** Calculate expected value
 *
 * Compute the expected value of a byte located at @pos in memory
 * area described by @area.
 *
 * @param area Memory area control structure
 * @param pos  Position in the memory area data area
 *
 */
static inline uint8_t area_expected_value(mem_area_t *area, uint8_t *pos)
{
	return ((uintptr_t) area ^ (uintptr_t) pos) & 0xaa;
}

/** Fill area
 *
 * Fill the memory area controlled by @area with data.
 *
 * @param area Memory area control structure
 *
 */
void fill_area(mem_area_t *area)
{
	for (uint8_t *pos = area->addr, *end = pos + area->size;
	    pos < end; pos++)
		*pos = area_expected_value(area, pos);
	
	check_consistency("fill_area");
}