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