source: mainline/uspace/app/tester/mm/malloc1.c@ 5462a30

/*
 * 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;
}