Changeset 82d56184 in mainline for uspace/app/tester/mm/malloc1.c


Ignore:
Timestamp:
2011-06-01T21:05:19Z (13 years ago)
Author:
Jakub Jermar <jakub@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
5cac9cd
Parents:
682cfceb (diff), 5d1b3aa (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge mainline changes.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • uspace/app/tester/mm/malloc1.c

    r682cfceb r82d56184  
    3030
    3131#include <stdio.h>
    32 #include <unistd.h>
    3332#include <stdlib.h>
    34 #include <malloc.h>
     33#include "common.h"
    3534#include "../tester.h"
    3635
    … …  
    4544 */
    4645
    47 /**
    48  * sizeof_array
    49  * @array array to determine the size of
    50  *
    51  * Returns the size of @array in array elements.
    52  */
    53 #define sizeof_array(array) \
    54         (sizeof(array) / sizeof((array)[0]))
    55 
    56 #define MAX_ALLOC (16 * 1024 * 1024)
    57 
    58 /*
    59  * Subphase control structures: subphase termination conditions,
    60  * probabilities of individual actions, subphase control structure.
    61  */
    62 
    63 typedef struct {
    64         unsigned int max_cycles;
    65         unsigned int no_memory;
    66         unsigned int no_allocated;
    67 } sp_term_cond_s;
    68 
    69 typedef struct {
    70         unsigned int alloc;
    71         unsigned int free;
    72 } sp_action_prob_s;
    73 
    74 typedef struct {
    75         const char *name;
    76         sp_term_cond_s cond;
    77         sp_action_prob_s prob;
    78 } subphase_s;
    79 
    80 
    81 /*
    82  * Phase control structures: The minimum and maximum block size that
    83  * can be allocated during the phase execution, phase control structure.
    84  */
    85 
    86 typedef struct {
    87         size_t min_block_size;
    88         size_t max_block_size;
    89 } ph_alloc_size_s;
    90 
    91 typedef struct {
    92         const char *name;
    93         ph_alloc_size_s alloc;
    94         subphase_s *subphases;
    95 } phase_s;
    96 
    97 
    9846/*
    9947 * Subphases are defined separately here. This is for two reasons:
    … …  
    10149 * how many subphases a phase contains.
    10250 */
    103 static subphase_s subphases_32B[] = {
     51static subphase_t subphases_32B[] = {
    10452        {
    10553                .name = "Allocation",
    … …  
    14088};
    14189
    142 static subphase_s subphases_128K[] = {
     90static subphase_t subphases_128K[] = {
    14391        {
    14492                .name = "Allocation",
    … …  
    179127};
    180128
    181 static subphase_s subphases_default[] = {
     129static subphase_t subphases_default[] = {
    182130        {
    183131                .name = "Allocation",
    … …  
    217165        }
    218166};
    219 
    220167
    221168/*
    222169 * Phase definitions.
    223170 */
    224 static phase_s phases[] = {
     171static phase_t phases[] = {
    225172        {
    226173                .name = "32 B memory blocks",
    … …  
    257204};
    258205
    259 
    260 /*
    261  * Global error flag. The flag is set if an error
    262  * is encountered (overlapping blocks, inconsistent
    263  * block data, etc.)
    264  */
    265 static bool error_flag = false;
    266 
    267 /*
    268  * Memory accounting: the amount of allocated memory and the
    269  * number and list of allocated blocks.
    270  */
    271 static size_t mem_allocated;
    272 static size_t mem_blocks_count;
    273 
    274 static LIST_INITIALIZE(mem_blocks);
    275 
    276 typedef struct {
    277         /* Address of the start of the block */
    278         void *addr;
    279        
    280         /* Size of the memory block */
    281         size_t size;
    282        
    283         /* link to other blocks */
    284         link_t link;
    285 } mem_block_s;
    286 
    287 typedef mem_block_s *mem_block_t;
    288 
    289 
    290 /** init_mem
    291  *
    292  * Initializes the memory accounting structures.
    293  *
    294  */
    295 static void init_mem(void)
     206static void do_subphase(phase_t *phase, subphase_t *subphase)
    296207{
    297         mem_allocated = 0;
    298         mem_blocks_count = 0;
    299 }
    300 
    301 
    302 static bool overlap_match(link_t *entry, void *addr, size_t size)
    303 {
    304         mem_block_t mblk = list_get_instance(entry, mem_block_s, link);
    305        
    306         /* Entry block control structure <mbeg, mend) */
    307         uint8_t *mbeg = (uint8_t *) mblk;
    308         uint8_t *mend = (uint8_t *) mblk + sizeof(mem_block_s);
    309        
    310         /* Entry block memory <bbeg, bend) */
    311         uint8_t *bbeg = (uint8_t *) mblk->addr;
    312         uint8_t *bend = (uint8_t *) mblk->addr + mblk->size;
    313        
    314         /* Data block <dbeg, dend) */
    315         uint8_t *dbeg = (uint8_t *) addr;
    316         uint8_t *dend = (uint8_t *) addr + size;
    317        
    318         /* Check for overlaps */
    319         if (((mbeg >= dbeg) && (mbeg < dend)) ||
    320                 ((mend > dbeg) && (mend <= dend)) ||
    321                 ((bbeg >= dbeg) && (bbeg < dend)) ||
    322                 ((bend > dbeg) && (bend <= dend)))
    323                 return true;
    324        
    325         return false;
    326 }
    327 
    328 
    329 /** test_overlap
    330  *
    331  * Test whether a block starting at @addr overlaps with another, previously
    332  * allocated memory block or its control structure.
    333  *
    334  * @param addr Initial address of the block
    335  * @param size Size of the block
    336  *
    337  * @return false if the block does not overlap.
    338  *
    339  */
    340 static int test_overlap(void *addr, size_t size)
    341 {
    342         link_t *entry;
    343         bool fnd = false;
    344        
    345         for (entry = mem_blocks.next; entry != &mem_blocks; entry = entry->next) {
    346                 if (overlap_match(entry, addr, size)) {
    347                         fnd = true;
    348                         break;
    349                 }
    350         }
    351        
    352         return fnd;
    353 }
    354 
    355 
    356 /** checked_malloc
    357  *
    358  * Allocate @size bytes of memory and check whether the chunk comes
    359  * from the non-mapped memory region and whether the chunk overlaps
    360  * with other, previously allocated, chunks.
    361  *
    362  * @param size Amount of memory to allocate
    363  *
    364  * @return NULL if the allocation failed. Sets the global error_flag to
    365  *         true if the allocation succeeded but is illegal.
    366  *
    367  */
    368 static void *checked_malloc(size_t size)
    369 {
    370         void *data;
    371        
    372         /* Allocate the chunk of memory */
    373         data = malloc(size);
    374         if (data == NULL)
    375                 return NULL;
    376        
    377         /* Check for overlaps with other chunks */
    378         if (test_overlap(data, size)) {
    379                 TPRINTF("\nError: Allocated block overlaps with another "
    380                         "previously allocated block.\n");
    381                 error_flag = true;
    382         }
    383        
    384         return data;
    385 }
    386 
    387 
    388 /** alloc_block
    389  *
    390  * Allocate a block of memory of @size bytes and add record about it into
    391  * the mem_blocks list. Return a pointer to the block holder structure or
    392  * NULL if the allocation failed.
    393  *
    394  * If the allocation is illegal (e.g. the memory does not come from the
    395  * right region or some of the allocated blocks overlap with others),
    396  * set the global error_flag.
    397  *
    398  * @param size Size of the memory block
    399  *
    400  */
    401 static mem_block_t alloc_block(size_t size)
    402 {
    403         /* Check for allocation limit */
    404         if (mem_allocated >= MAX_ALLOC)
    405                 return NULL;
    406        
    407         /* Allocate the block holder */
    408         mem_block_t block = (mem_block_t) checked_malloc(sizeof(mem_block_s));
    409         if (block == NULL)
    410                 return NULL;
    411        
    412         link_initialize(&block->link);
    413        
    414         /* Allocate the block memory */
    415         block->addr = checked_malloc(size);
    416         if (block->addr == NULL) {
    417                 free(block);
    418                 return NULL;
    419         }
    420        
    421         block->size = size;
    422        
    423         /* Register the allocated block */
    424         list_append(&block->link, &mem_blocks);
    425         mem_allocated += size + sizeof(mem_block_s);
    426         mem_blocks_count++;
    427        
    428         return block;
    429 }
    430 
    431 
    432 /** free_block
    433  *
    434  * Free the block of memory and the block control structure allocated by
    435  * alloc_block. Set the global error_flag if an error occurs.
    436  *
    437  * @param block Block control structure
    438  *
    439  */
    440 static void free_block(mem_block_t block)
    441 {
    442         /* Unregister the block */
    443         list_remove(&block->link);
    444         mem_allocated -= block->size + sizeof(mem_block_s);
    445         mem_blocks_count--;
    446        
    447         /* Free the memory */
    448         free(block->addr);
    449         free(block);
    450 }
    451 
    452 
    453 /** expected_value
    454  *
    455  * Compute the expected value of a byte located at @pos in memory
    456  * block described by @blk.
    457  *
    458  * @param blk Memory block control structure
    459  * @param pos Position in the memory block data area
    460  *
    461  */
    462 static inline uint8_t expected_value(mem_block_t blk, uint8_t *pos)
    463 {
    464         return ((unsigned long) blk ^ (unsigned long) pos) & 0xff;
    465 }
    466 
    467 
    468 /** fill_block
    469  *
    470  * Fill the memory block controlled by @blk with data.
    471  *
    472  * @param blk Memory block control structure
    473  *
    474  */
    475 static void fill_block(mem_block_t blk)
    476 {
    477         uint8_t *pos;
    478         uint8_t *end;
    479        
    480         for (pos = blk->addr, end = pos + blk->size; pos < end; pos++)
    481                 *pos = expected_value(blk, pos);
    482 }
    483 
    484 
    485 /** check_block
    486  *
    487  * Check whether the block @blk contains the data it was filled with.
    488  * Set global error_flag if an error occurs.
    489  *
    490  * @param blk Memory block control structure
    491  *
    492  */
    493 static void check_block(mem_block_t blk)
    494 {
    495         uint8_t *pos;
    496         uint8_t *end;
    497        
    498         for (pos = blk->addr, end = pos + blk->size; pos < end; pos++) {
    499                 if (*pos != expected_value (blk, pos)) {
    500                         TPRINTF("\nError: Corrupted content of a data block.\n");
    501                         error_flag = true;
    502                         return;
    503                 }
    504         }
    505 }
    506 
    507 
    508 static link_t *list_get_nth(link_t *list, unsigned int i)
    509 {
    510         unsigned int cnt = 0;
    511         link_t *entry;
    512        
    513         for (entry = list->next; entry != list; entry = entry->next) {
    514                 if (cnt == i)
    515                         return entry;
    516                
    517                 cnt++;
    518         }
    519        
    520         return NULL;
    521 }
    522 
    523 
    524 /** get_random_block
    525  *
    526  * Select a random memory block from the list of allocated blocks.
    527  *
    528  * @return Block control structure or NULL if the list is empty.
    529  *
    530  */
    531 static mem_block_t get_random_block(void)
    532 {
    533         if (mem_blocks_count == 0)
    534                 return NULL;
    535        
    536         unsigned int blkidx = rand() % mem_blocks_count;
    537         link_t *entry = list_get_nth(&mem_blocks, blkidx);
    538        
    539         if (entry == NULL) {
    540                 TPRINTF("\nError: Corrupted list of allocated memory blocks.\n");
    541                 error_flag = true;
    542         }
    543        
    544         return list_get_instance(entry, mem_block_s, link);
    545 }
    546 
    547 
    548 #define RETURN_IF_ERROR \
    549 { \
    550         if (error_flag) \
    551                 return; \
    552 }
    553 
    554 
    555 static void do_subphase(phase_s *phase, subphase_s *subphase)
    556 {
    557         unsigned int cycles;
    558         for (cycles = 0; /* always */; cycles++) {
    559                
    560                 if (subphase->cond.max_cycles &&
    561                         cycles >= subphase->cond.max_cycles) {
     208        for (unsigned int cycles = 0; /* always */; cycles++) {
     209               
     210                if ((subphase->cond.max_cycles) &&
     211                    (cycles >= subphase->cond.max_cycles)) {
    562212                        /*
    563213                         * We have performed the required number of
    … …  
    572222                unsigned int rnd = rand() % 100;
    573223                if (rnd < subphase->prob.alloc) {
    574                         /* Compute a random number lying in interval <min_block_size, max_block_size> */
     224                        /*
     225                         * Compute a random number lying in interval
     226                         * <min_block_size, max_block_size>
     227                         */
    575228                        int alloc = phase->alloc.min_block_size +
    576229                            (rand() % (phase->alloc.max_block_size - phase->alloc.min_block_size + 1));
    577230                       
    578                         mem_block_t blk = alloc_block(alloc);
     231                        mem_block_t *blk = alloc_block(alloc);
    579232                        RETURN_IF_ERROR;
    580233                       
    … …  
    585238                                        break;
    586239                                }
    587                                
    588240                        } else {
    589241                                TPRINTF("A");
    590242                                fill_block(blk);
     243                                RETURN_IF_ERROR;
    591244                        }
    592245                       
    593246                } else if (rnd < subphase->prob.free) {
    594                         mem_block_t blk = get_random_block();
     247                        mem_block_t *blk = get_random_block();
    595248                        if (blk == NULL) {
    596249                                TPRINTF("F(R)");
    … …  
    599252                                        break;
    600253                                }
    601                                
    602254                        } else {
    603255                                TPRINTF("R");
    … …  
    614266}
    615267
    616 
    617 static void do_phase(phase_s *phase)
     268static void do_phase(phase_t *phase)
    618269{
    619         unsigned int subno;
    620        
    621         for (subno = 0; subno < 3; subno++) {
    622                 subphase_s *subphase = & phase->subphases [subno];
     270        for (unsigned int subno = 0; subno < 3; subno++) {
     271                subphase_t *subphase = &phase->subphases[subno];
    623272               
    624273                TPRINTF(".. Sub-phase %u (%s)\n", subno + 1, subphase->name);
    … …  
    632281        init_mem();
    633282       
    634         unsigned int phaseno;
    635         for (phaseno = 0; phaseno < sizeof_array(phases); phaseno++) {
    636                 phase_s *phase = &phases[phaseno];
     283        for (unsigned int phaseno = 0; phaseno < sizeof_array(phases);
     284            phaseno++) {
     285                phase_t *phase = &phases[phaseno];
    637286               
    638287                TPRINTF("Entering phase %u (%s)\n", phaseno + 1, phase->name);
    … …  
    645294        }
    646295       
     296        TPRINTF("Cleaning up.\n");
     297        done_mem();
    647298        if (error_flag)
    648299                return "Test failed";
Note: See TracChangeset for help on using the changeset viewer.