Subversion Repositories HelenOS

Rev

Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Copyright (c) 2009 Martin Decky
  3.  * Copyright (c) 2009 Tomas Bures
  4.  * Copyright (c) 2009 Lubomir Bulej
  5.  * All rights reserved.
  6.  *
  7.  * Redistribution and use in source and binary forms, with or without
  8.  * modification, are permitted provided that the following conditions
  9.  * are met:
  10.  *
  11.  * - Redistributions of source code must retain the above copyright
  12.  *   notice, this list of conditions and the following disclaimer.
  13.  * - Redistributions in binary form must reproduce the above copyright
  14.  *   notice, this list of conditions and the following disclaimer in the
  15.  *   documentation and/or other materials provided with the distribution.
  16.  * - The name of the author may not be used to endorse or promote products
  17.  *   derived from this software without specific prior written permission.
  18.  *
  19.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  20.  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  21.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  22.  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  23.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  24.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25.  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26.  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27.  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  28.  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29.  */
  30.  
  31. #include <stdio.h>
  32. #include <unistd.h>
  33. #include <stdlib.h>
  34. #include <malloc.h>
  35. #include "../tester.h"
  36.  
  37. /*
  38.  * The test consists of several phases which differ in the size of blocks
  39.  * they allocate. The size of blocks is given as a range of minimum and
  40.  * maximum allowed size. Each of the phases is divided into 3 subphases which
  41.  * differ in the probability of free and alloc actions. Second subphase is
  42.  * started when malloc returns 'out of memory' or when MAX_ALLOC is reached.
  43.  * Third subphase is started after a given number of cycles. The third subphase
  44.  * as well as the whole phase ends when all memory blocks are released.
  45.  */
  46.  
  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.     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.     char *name;
  93.     ph_alloc_size_s alloc;
  94.     subphase_s *subphases;
  95. } phase_s;
  96.  
  97.  
  98. /*
  99.  * Subphases are defined separately here. This is for two reasons:
  100.  * 1) data are not duplicated, 2) we don't have to state beforehand
  101.  * how many subphases a phase contains.
  102.  */
  103. static subphase_s subphases_32B[] = {
  104.     {
  105.         .name = "Allocation",
  106.         .cond = {
  107.             .max_cycles = 200,
  108.             .no_memory = 1,
  109.             .no_allocated = 0,
  110.         },
  111.         .prob = {
  112.             .alloc = 90,
  113.             .free = 100
  114.         }
  115.     },
  116.     {
  117.         .name = "Alloc/Dealloc",
  118.         .cond = {
  119.             .max_cycles = 200,
  120.             .no_memory = 0,
  121.             .no_allocated = 0,
  122.         },
  123.         .prob = {
  124.             .alloc = 50,
  125.             .free = 100
  126.         }
  127.     },
  128.     {
  129.         .name = "Deallocation",
  130.         .cond = {
  131.             .max_cycles = 0,
  132.             .no_memory = 0,
  133.             .no_allocated = 1,
  134.         },
  135.         .prob = {
  136.             .alloc = 10,
  137.             .free = 100
  138.         }
  139.     }
  140. };
  141.  
  142. static subphase_s subphases_128K[] = {
  143.     {
  144.         .name = "Allocation",
  145.         .cond = {
  146.             .max_cycles = 0,
  147.             .no_memory = 1,
  148.             .no_allocated = 0,
  149.         },
  150.         .prob = {
  151.             .alloc = 70,
  152.             .free = 100
  153.         }
  154.     },
  155.     {
  156.         .name = "Alloc/Dealloc",
  157.         .cond = {
  158.             .max_cycles = 30,
  159.             .no_memory = 0,
  160.             .no_allocated = 0,
  161.         },
  162.         .prob = {
  163.             .alloc = 50,
  164.             .free = 100
  165.         }
  166.     },
  167.     {
  168.         .name = "Deallocation",
  169.         .cond = {
  170.             .max_cycles = 0,
  171.             .no_memory = 0,
  172.             .no_allocated = 1,
  173.         },
  174.         .prob = {
  175.             .alloc = 30,
  176.             .free = 100
  177.         }
  178.     }
  179. };
  180.  
  181. static subphase_s subphases_default[] = {
  182.     {
  183.         .name = "Allocation",
  184.         .cond = {
  185.             .max_cycles = 0,
  186.             .no_memory = 1,
  187.             .no_allocated = 0,
  188.         },
  189.         .prob = {
  190.             .alloc = 90,
  191.             .free = 100
  192.         }
  193.     },
  194.     {
  195.         .name = "Alloc/Dealloc",
  196.         .cond = {
  197.             .max_cycles = 200,
  198.             .no_memory = 0,
  199.             .no_allocated = 0,
  200.         },
  201.         .prob = {
  202.             .alloc = 50,
  203.             .free = 100
  204.         }
  205.     },
  206.     {
  207.         .name = "Deallocation",
  208.         .cond = {
  209.             .max_cycles = 0,
  210.             .no_memory = 0,
  211.             .no_allocated = 1,
  212.         },
  213.         .prob = {
  214.             .alloc = 10,
  215.             .free = 100
  216.         }
  217.     }
  218. };
  219.  
  220.  
  221. /*
  222.  * Phase definitions.
  223.  */
  224. static phase_s phases[] = {
  225.     {
  226.         .name = "32 B memory blocks",
  227.         .alloc = {
  228.             .min_block_size = 32,
  229.             .max_block_size = 32
  230.         },
  231.         .subphases = subphases_32B
  232.     },
  233.     {
  234.         .name = "128 KB memory blocks",
  235.         .alloc = {
  236.             .min_block_size = 128 * 1024,
  237.             .max_block_size = 128 * 1024
  238.         },
  239.         .subphases = subphases_128K
  240.     },
  241.     {
  242.         .name = "2500 B memory blocks",
  243.         .alloc = {
  244.             .min_block_size = 2500,
  245.             .max_block_size = 2500
  246.         },
  247.         .subphases = subphases_default
  248.     },
  249.     {
  250.         .name = "1 B .. 250000 B memory blocks",
  251.         .alloc = {
  252.             .min_block_size = 1,
  253.             .max_block_size = 250000
  254.         },
  255.         .subphases = subphases_default
  256.     }
  257. };
  258.  
  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)
  296. {
  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) {
  562.             /*
  563.              * We have performed the required number of
  564.              * cycles. End the current subphase.
  565.              */
  566.             break;
  567.         }
  568.        
  569.         /*
  570.          * Decide whether we alloc or free memory in this step.
  571.          */
  572.         unsigned int rnd = rand() % 100;
  573.         if (rnd < subphase->prob.alloc) {
  574.             /* Compute a random number lying in interval <min_block_size, max_block_size> */
  575.             int alloc = phase->alloc.min_block_size +
  576.                 (rand() % (phase->alloc.max_block_size - phase->alloc.min_block_size + 1));
  577.            
  578.             mem_block_t blk = alloc_block(alloc);
  579.             RETURN_IF_ERROR;
  580.            
  581.             if (blk == NULL) {
  582.                 TPRINTF("F(A)");
  583.                 if (subphase->cond.no_memory) {
  584.                     /* We filled the memory. Proceed to next subphase */
  585.                     break;
  586.                 }
  587.                
  588.             } else {
  589.                 TPRINTF("A");
  590.                 fill_block(blk);
  591.             }
  592.            
  593.         } else if (rnd < subphase->prob.free) {
  594.             mem_block_t blk = get_random_block();
  595.             if (blk == NULL) {
  596.                 TPRINTF("F(R)");
  597.                 if (subphase->cond.no_allocated) {
  598.                     /* We free all the memory. Proceed to next subphase. */
  599.                     break;
  600.                 }
  601.                
  602.             } else {
  603.                 TPRINTF("R");
  604.                 check_block(blk);
  605.                 RETURN_IF_ERROR;
  606.                
  607.                 free_block(blk);
  608.                 RETURN_IF_ERROR;
  609.             }
  610.         }
  611.     }
  612.    
  613.     TPRINTF("\n..  finished.\n");
  614. }
  615.  
  616.  
  617. static void do_phase(phase_s *phase)
  618. {
  619.     unsigned int subno;
  620.    
  621.     for (subno = 0; subno < 3; subno++) {
  622.         subphase_s *subphase = & phase->subphases [subno];
  623.        
  624.         TPRINTF(".. Sub-phase %u (%s)\n", subno + 1, subphase->name);
  625.         do_subphase(phase, subphase);
  626.         RETURN_IF_ERROR;
  627.     }
  628. }
  629.  
  630. char *test_malloc1(void)
  631. {
  632.     init_mem();
  633.    
  634.     unsigned int phaseno;
  635.     for (phaseno = 0; phaseno < sizeof_array(phases); phaseno++) {
  636.         phase_s *phase = &phases[phaseno];
  637.        
  638.         TPRINTF("Entering phase %u (%s)\n", phaseno + 1, phase->name);
  639.        
  640.         do_phase(phase);
  641.         if (error_flag)
  642.             break;
  643.        
  644.         TPRINTF("Phase finished.\n");
  645.     }
  646.    
  647.     if (error_flag)
  648.         return "Test failed";
  649.    
  650.     return NULL;
  651. }
  652.