Index: uspace/app/tester/mm/malloc1.c
===================================================================
--- uspace/app/tester/mm/malloc1.c	(revision 6db6fd18c6afe2f2ade4f934e820a461a6f232bc)
+++ uspace/app/tester/mm/malloc1.c	(revision 6db6fd18c6afe2f2ade4f934e820a461a6f232bc)
@@ -0,0 +1,651 @@
+/*
+ * 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 {
+	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 {
+	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;
+	}
+}
+
+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;
+}
Index: uspace/app/tester/mm/malloc1.def
===================================================================
--- uspace/app/tester/mm/malloc1.def	(revision 6db6fd18c6afe2f2ade4f934e820a461a6f232bc)
+++ uspace/app/tester/mm/malloc1.def	(revision 6db6fd18c6afe2f2ade4f934e820a461a6f232bc)
@@ -0,0 +1,6 @@
+{
+	"malloc1",
+	"Memory allocator test",
+	&test_malloc1,
+	true
+},