source: mainline/uspace/app/tester/mm/common.c@ 1b3e854

/*
 * 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_head(&mem_blocks)) != NULL) {
                mem_block_t *block = list_get_instance(link, mem_block_t, link);
                free_block(block);
        }
        
        while ((link = list_head(&mem_areas)) != NULL) {
                mem_area_t *area = list_get_instance(link, mem_area_t, link);
                unmap_area(area);
        }
}

static bool overlap_match(link_t *link, void *addr, size_t size)
{
        mem_block_t *block = list_get_instance(link, mem_block_t, link);
        
        /* 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) {
                if (overlap_match(link, 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 int 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);
        
        /* Map the memory area */
        void *addr = as_get_mappable_page(size);
        if (addr == NULL) {
                free(area);
                check_consistency("map_area (a)");
                return NULL;
        }
        
        area->addr = as_area_create(addr, size, AS_AREA_WRITE | AS_AREA_READ);
        if (area->addr == (void *) -1) {
                free(area);
                check_consistency("map_area (b)");
                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");
}