/*
 * 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 <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <malloc.h>
#include "../tester.h"

/*
 * The test consists of several phases which differ in the size of blocks
 * they allocate. The size of blocks is given as a range of minimum and
 * maximum allowed size. Each of the phases is divided into 3 subphases which
 * differ in the probability of free and alloc actions. Second subphase is
 * started when malloc returns 'out of memory' or when MAX_ALLOC is reached.
 * Third subphase is started after a given number of cycles. The third subphase
 * as well as the whole phase ends when all memory blocks are released.
 */

/**
 * sizeof_array
 * @array array to determine the size of
 *
 * Returns the size of @array in array elements.
 */
#define sizeof_array(array) \
	(sizeof(array) / sizeof((array)[0]))

#define MAX_ALLOC (16 * 1024 * 1024)

/*
 * Subphase control structures: subphase termination conditions,
 * probabilities of individual actions, subphase control structure.
 */

typedef struct {
	unsigned int max_cycles;
	unsigned int no_memory;
	unsigned int no_allocated;
} sp_term_cond_s;

typedef struct {
	unsigned int alloc;
	unsigned int free;
} sp_action_prob_s;

typedef struct {
	const char *name;
	sp_term_cond_s cond;
	sp_action_prob_s prob;
} subphase_s;


/*
 * Phase control structures: The minimum and maximum block size that
 * can be allocated during the phase execution, phase control structure.
 */

typedef struct {
	size_t min_block_size;
	size_t max_block_size;
} ph_alloc_size_s;

typedef struct {
	const char *name;
	ph_alloc_size_s alloc;
	subphase_s *subphases;
} phase_s;


/*
 * Subphases are defined separately here. This is for two reasons:
 * 1) data are not duplicated, 2) we don't have to state beforehand
 * how many subphases a phase contains.
 */
static subphase_s subphases_32B[] = {
	{
		.name = "Allocation",
		.cond = {
			.max_cycles = 200,
			.no_memory = 1,
			.no_allocated = 0,
		},
		.prob = {
			.alloc = 90,
			.free = 100
		}
	},
	{
		.name = "Alloc/Dealloc",
		.cond = {
			.max_cycles = 200,
			.no_memory = 0,
			.no_allocated = 0,
		},
		.prob = {
			.alloc = 50,
			.free = 100
		}
	},
	{
		.name = "Deallocation",
		.cond = {
			.max_cycles = 0,
			.no_memory = 0,
			.no_allocated = 1,
		},
		.prob = {
			.alloc = 10,
			.free = 100
		}
	}
};

static subphase_s subphases_128K[] = {
	{
		.name = "Allocation",
		.cond = {
			.max_cycles = 0,
			.no_memory = 1,
			.no_allocated = 0,
		},
		.prob = {
			.alloc = 70,
			.free = 100
		}
	},
	{
		.name = "Alloc/Dealloc",
		.cond = {
			.max_cycles = 30,
			.no_memory = 0,
			.no_allocated = 0,
		},
		.prob = {
			.alloc = 50,
			.free = 100
		}
	},
	{
		.name = "Deallocation",
		.cond = {
			.max_cycles = 0,
			.no_memory = 0,
			.no_allocated = 1,
		},
		.prob = {
			.alloc = 30,
			.free = 100
		}
	}
};

static subphase_s subphases_default[] = {
	{
		.name = "Allocation",
		.cond = {
			.max_cycles = 0,
			.no_memory = 1,
			.no_allocated = 0,
		},
		.prob = {
			.alloc = 90,
			.free = 100
		}
	},
	{
		.name = "Alloc/Dealloc",
		.cond = {
			.max_cycles = 200,
			.no_memory = 0,
			.no_allocated = 0,
		},
		.prob = {
			.alloc = 50,
			.free = 100
		}
	},
	{
		.name = "Deallocation",
		.cond = {
			.max_cycles = 0,
			.no_memory = 0,
			.no_allocated = 1,
		},
		.prob = {
			.alloc = 10,
			.free = 100
		}
	}
};


/*
 * Phase definitions.
 */
static phase_s phases[] = {
	{
		.name = "32 B memory blocks",
		.alloc = {
			.min_block_size = 32,
			.max_block_size = 32
		},
		.subphases = subphases_32B
	},
	{
		.name = "128 KB memory blocks",
		.alloc = {
			.min_block_size = 128 * 1024,
			.max_block_size = 128 * 1024
		},
		.subphases = subphases_128K
	},
	{
		.name = "2500 B memory blocks",
		.alloc = {
			.min_block_size = 2500,
			.max_block_size = 2500
		},
		.subphases = subphases_default
	},
	{
		.name = "1 B .. 250000 B memory blocks",
		.alloc = {
			.min_block_size = 1,
			.max_block_size = 250000
		},
		.subphases = subphases_default
	}
};


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

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

static LIST_INITIALIZE(mem_blocks);

typedef struct {
	/* Address of the start of the block */
	void *addr;
	
	/* Size of the memory block */
	size_t size;
	
	/* link to other blocks */
	link_t link;
} mem_block_s;

typedef mem_block_s *mem_block_t;


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


static bool overlap_match(link_t *entry, void *addr, size_t size)
{
	mem_block_t mblk = list_get_instance(entry, mem_block_s, link);
	
	/* Entry block control structure <mbeg, mend) */
	uint8_t *mbeg = (uint8_t *) mblk;
	uint8_t *mend = (uint8_t *) mblk + sizeof(mem_block_s);
	
	/* Entry block memory <bbeg, bend) */
	uint8_t *bbeg = (uint8_t *) mblk->addr;
	uint8_t *bend = (uint8_t *) mblk->addr + mblk->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)
{
	link_t *entry;
	bool fnd = false;
	
	for (entry = mem_blocks.next; entry != &mem_blocks; entry = entry->next) {
		if (overlap_match(entry, addr, size)) {
			fnd = true;
			break;
		}
	}
	
	return fnd;
}


/** 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);
	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");
		error_flag = true;
	}
	
	return data;
}


/** alloc_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
 *
 */
static 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_s));
	if (block == NULL)
		return NULL;
	
	link_initialize(&block->link);
	
	/* Allocate the block memory */
	block->addr = checked_malloc(size);
	if (block->addr == NULL) {
		free(block);
		return NULL;
	}
	
	block->size = size;
	
	/* Register the allocated block */
	list_append(&block->link, &mem_blocks);
	mem_allocated += size + sizeof(mem_block_s);
	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
 *
 */
static void free_block(mem_block_t block)
{
	/* Unregister the block */
	list_remove(&block->link);
	mem_allocated -= block->size + sizeof(mem_block_s);
	mem_blocks_count--;
	
	/* Free the memory */
	free(block->addr);
	free(block);
}


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


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


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


static link_t *list_get_nth(link_t *list, unsigned int i)
{
	unsigned int cnt = 0;
	link_t *entry;
	
	for (entry = list->next; entry != list; entry = entry->next) {
		if (cnt == i)
			return entry;
		
		cnt++;
	}
	
	return NULL;
}


/** 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.
 *
 */
static mem_block_t get_random_block(void)
{
	if (mem_blocks_count == 0)
		return NULL;
	
	unsigned int blkidx = rand() % mem_blocks_count;
	link_t *entry = list_get_nth(&mem_blocks, blkidx);
	
	if (entry == NULL) {
		TPRINTF("\nError: Corrupted list of allocated memory blocks.\n");
		error_flag = true;
	}
	
	return list_get_instance(entry, mem_block_s, link);
}


#define RETURN_IF_ERROR \
{ \
	if (error_flag) \
		return; \
}


static void do_subphase(phase_s *phase, subphase_s *subphase)
{
	unsigned int cycles;
	for (cycles = 0; /* always */; cycles++) {
		
		if (subphase->cond.max_cycles &&
			cycles >= subphase->cond.max_cycles) {
			/*
			 * We have performed the required number of
			 * cycles. End the current subphase.
			 */
			break;
		}
		
		/*
		 * Decide whether we alloc or free memory in this step.
		 */
		unsigned int rnd = rand() % 100;
		if (rnd < subphase->prob.alloc) {
			/* Compute a random number lying in interval <min_block_size, max_block_size> */
			int alloc = phase->alloc.min_block_size +
			    (rand() % (phase->alloc.max_block_size - phase->alloc.min_block_size + 1));
			
			mem_block_t blk = alloc_block(alloc);
			RETURN_IF_ERROR;
			
			if (blk == NULL) {
				TPRINTF("F(A)");
				if (subphase->cond.no_memory) {
					/* We filled the memory. Proceed to next subphase */
					break;
				}
				
			} else {
				TPRINTF("A");
				fill_block(blk);
			}
			
		} else if (rnd < subphase->prob.free) {
			mem_block_t blk = get_random_block();
			if (blk == NULL) {
				TPRINTF("F(R)");
				if (subphase->cond.no_allocated) {
					/* We free all the memory. Proceed to next subphase. */
					break;
				}
				
			} else {
				TPRINTF("R");
				check_block(blk);
				RETURN_IF_ERROR;
				
				free_block(blk);
				RETURN_IF_ERROR;
			}
		}
	}
	
	TPRINTF("\n..  finished.\n");
}


static void do_phase(phase_s *phase)
{
	unsigned int subno;
	
	for (subno = 0; subno < 3; subno++) {
		subphase_s *subphase = & phase->subphases [subno];
		
		TPRINTF(".. Sub-phase %u (%s)\n", subno + 1, subphase->name);
		do_subphase(phase, subphase);
		RETURN_IF_ERROR;
	}
}

const char *test_malloc1(void)
{
	init_mem();
	
	unsigned int phaseno;
	for (phaseno = 0; phaseno < sizeof_array(phases); phaseno++) {
		phase_s *phase = &phases[phaseno];
		
		TPRINTF("Entering phase %u (%s)\n", phaseno + 1, phase->name);
		
		do_phase(phase);
		if (error_flag)
			break;
		
		TPRINTF("Phase finished.\n");
	}
	
	if (error_flag)
		return "Test failed";
	
	return NULL;
}