Subversion Repositories HelenOS

Rev

Rev 4643 | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Copyright (c) 2009 Martin Decky
  3.  * Copyright (c) 2009 Petr Tuma
  4.  * All rights reserved.
  5.  *
  6.  * Redistribution and use in source and binary forms, with or without
  7.  * modification, are permitted provided that the following conditions
  8.  * are met:
  9.  *
  10.  * - Redistributions of source code must retain the above copyright
  11.  *   notice, this list of conditions and the following disclaimer.
  12.  * - Redistributions in binary form must reproduce the above copyright
  13.  *   notice, this list of conditions and the following disclaimer in the
  14.  *   documentation and/or other materials provided with the distribution.
  15.  * - The name of the author may not be used to endorse or promote products
  16.  *   derived from this software without specific prior written permission.
  17.  *
  18.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  19.  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  20.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  21.  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  22.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  23.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24.  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25.  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26.  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  27.  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28.  */
  29.  
  30. /** @addtogroup libc
  31.  * @{
  32.  */
  33. /** @file
  34.  */
  35.  
  36. #include <malloc.h>
  37. #include <bool.h>
  38. #include <as.h>
  39. #include <align.h>
  40. #include <macros.h>
  41. #include <assert.h>
  42. #include <errno.h>
  43. #include <bitops.h>
  44. #include <mem.h>
  45. #include <adt/gcdlcm.h>
  46.  
  47. /* Magic used in heap headers. */
  48. #define HEAP_BLOCK_HEAD_MAGIC  0xBEEF0101
  49.  
  50. /* Magic used in heap footers. */
  51. #define HEAP_BLOCK_FOOT_MAGIC  0xBEEF0202
  52.  
  53. /** Allocation alignment (this also covers the alignment of fields
  54.     in the heap header and footer) */
  55. #define BASE_ALIGN  16
  56.  
  57. /**
  58.  * Either 4 * 256M on 32-bit architecures or 16 * 256M on 64-bit architectures
  59.  */
  60. #define MAX_HEAP_SIZE  (sizeof(uintptr_t) << 28)
  61.  
  62. /**
  63.  *
  64.  */
  65. #define STRUCT_OVERHEAD  (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t))
  66.  
  67. /**
  68.  * Calculate real size of a heap block (with header and footer)
  69.  */
  70. #define GROSS_SIZE(size)  ((size) + STRUCT_OVERHEAD)
  71.  
  72. /**
  73.  * Calculate net size of a heap block (without header and footer)
  74.  */
  75. #define NET_SIZE(size)  ((size) - STRUCT_OVERHEAD)
  76.  
  77.  
  78. /** Header of a heap block
  79.  *
  80.  */
  81. typedef struct {
  82.     /* Size of the block (including header and footer) */
  83.     size_t size;
  84.    
  85.     /* Indication of a free block */
  86.     bool free;
  87.    
  88.     /* A magic value to detect overwrite of heap header */
  89.     uint32_t magic;
  90. } heap_block_head_t;
  91.  
  92. /** Footer of a heap block
  93.  *
  94.  */
  95. typedef struct {
  96.     /* Size of the block (including header and footer) */
  97.     size_t size;
  98.    
  99.     /* A magic value to detect overwrite of heap footer */
  100.     uint32_t magic;
  101. } heap_block_foot_t;
  102.  
  103. /** Linker heap symbol */
  104. extern char _heap;
  105.  
  106. /** Address of heap start */
  107. static void *heap_start = 0;
  108.  
  109. /** Address of heap end */
  110. static void *heap_end = 0;
  111.  
  112. /** Maximum heap size */
  113. static size_t max_heap_size = (size_t) -1;
  114.  
  115. /** Current number of pages of heap area */
  116. static size_t heap_pages = 0;
  117.  
  118. /** Initialize a heap block
  119.  *
  120.  * Fills in the structures related to a heap block.
  121.  *
  122.  * @param addr Address of the block.
  123.  * @param size Size of the block including the header and the footer.
  124.  * @param free Indication of a free block.
  125.  *
  126.  */
  127. static void block_init(void *addr, size_t size, bool free)
  128. {
  129.     /* Calculate the position of the header and the footer */
  130.     heap_block_head_t *head = (heap_block_head_t *) addr;
  131.     heap_block_foot_t *foot =
  132.         (heap_block_foot_t *) (addr + size - sizeof(heap_block_foot_t));
  133.    
  134.     head->size = size;
  135.     head->free = free;
  136.     head->magic = HEAP_BLOCK_HEAD_MAGIC;
  137.    
  138.     foot->size = size;
  139.     foot->magic = HEAP_BLOCK_FOOT_MAGIC;
  140. }
  141.  
  142. /** Check a heap block
  143.  *
  144.  * Verifies that the structures related to a heap block still contain
  145.  * the magic constants. This helps detect heap corruption early on.
  146.  *
  147.  * @param addr Address of the block.
  148.  *
  149.  */
  150. static void block_check(void *addr)
  151. {
  152.     heap_block_head_t *head = (heap_block_head_t *) addr;
  153.    
  154.     assert(head->magic == HEAP_BLOCK_HEAD_MAGIC);
  155.    
  156.     heap_block_foot_t *foot =
  157.         (heap_block_foot_t *) (addr + head->size - sizeof(heap_block_foot_t));
  158.    
  159.     assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC);
  160.     assert(head->size == foot->size);
  161. }
  162.  
  163. static bool grow_heap(size_t size)
  164. {
  165.     if (size == 0)
  166.         return false;
  167.    
  168.     size_t heap_size = (size_t) (heap_end - heap_start);
  169.    
  170.     if ((max_heap_size != (size_t) -1) && (heap_size + size > max_heap_size))
  171.         return false;
  172.    
  173.     size_t pages = (size - 1) / PAGE_SIZE + 1;
  174.    
  175.     if (as_area_resize((void *) &_heap, (heap_pages + pages) * PAGE_SIZE, 0)
  176.         == EOK) {
  177.         void *end = (void *) ALIGN_DOWN(((uintptr_t) &_heap) +
  178.             (heap_pages + pages) * PAGE_SIZE, BASE_ALIGN);
  179.         block_init(heap_end, end - heap_end, true);
  180.         heap_pages += pages;
  181.         heap_end = end;
  182.         return true;
  183.     }
  184.    
  185.     return false;
  186. }
  187.  
  188. static void shrink_heap(void)
  189. {
  190.     // TODO
  191. }
  192.  
  193. /** Initialize the heap allocator
  194.  *
  195.  * Finds how much physical memory we have and creates
  196.  * the heap management structures that mark the whole
  197.  * physical memory as a single free block.
  198.  *
  199.  */
  200. void __heap_init(void)
  201. {
  202.     if (as_area_create((void *) &_heap, PAGE_SIZE,
  203.         AS_AREA_WRITE | AS_AREA_READ)) {
  204.         heap_pages = 1;
  205.         heap_start = (void *) ALIGN_UP((uintptr_t) &_heap, BASE_ALIGN);
  206.         heap_end =
  207.             (void *) ALIGN_DOWN(((uintptr_t) &_heap) + PAGE_SIZE, BASE_ALIGN);
  208.        
  209.         /* Make the entire area one large block. */
  210.         block_init(heap_start, heap_end - heap_start, true);
  211.     }
  212. }
  213.  
  214. uintptr_t get_max_heap_addr(void)
  215. {
  216.     if (max_heap_size == (size_t) -1)
  217.         max_heap_size =
  218.             max((size_t) (heap_end - heap_start), MAX_HEAP_SIZE);
  219.    
  220.     return ((uintptr_t) heap_start + max_heap_size);
  221. }
  222.  
  223. static void split_mark(heap_block_head_t *cur, const size_t size)
  224. {
  225.     assert(cur->size >= size);
  226.    
  227.     /* See if we should split the block. */
  228.     size_t split_limit = GROSS_SIZE(size);
  229.    
  230.     if (cur->size > split_limit) {
  231.         /* Block big enough -> split. */
  232.         void *next = ((void *) cur) + size;
  233.         block_init(next, cur->size - size, true);
  234.         block_init(cur, size, false);
  235.     } else {
  236.         /* Block too small -> use as is. */
  237.         cur->free = false;
  238.     }
  239. }
  240.  
  241. /** Allocate a memory block
  242.  *
  243.  * @param size  The size of the block to allocate.
  244.  * @param align Memory address alignment.
  245.  *
  246.  * @return the address of the block or NULL when not enough memory.
  247.  *
  248.  */
  249. static void *malloc_internal(const size_t size, const size_t align)
  250. {
  251.     if (align == 0)
  252.         return NULL;
  253.    
  254.     size_t falign = lcm(align, BASE_ALIGN);
  255.     size_t real_size = GROSS_SIZE(ALIGN_UP(size, falign));
  256.    
  257.     bool grown = false;
  258.     void *result;
  259.    
  260. loop:
  261.     result = NULL;
  262.     heap_block_head_t *cur = (heap_block_head_t *) heap_start;
  263.    
  264.     while ((result == NULL) && ((void *) cur < heap_end)) {
  265.         block_check(cur);
  266.        
  267.         /* Try to find a block that is free and large enough. */
  268.         if ((cur->free) && (cur->size >= real_size)) {
  269.             /* We have found a suitable block.
  270.                Check for alignment properties. */
  271.             void *addr = ((void *) cur) + sizeof(heap_block_head_t);
  272.             void *aligned = (void *) ALIGN_UP(addr, falign);
  273.            
  274.             if (addr == aligned) {
  275.                 /* Exact block start including alignment. */
  276.                 split_mark(cur, real_size);
  277.                 result = addr;
  278.             } else {
  279.                 /* Block start has to be aligned */
  280.                 size_t excess = (size_t) (aligned - addr);
  281.                
  282.                 if (cur->size >= real_size + excess) {
  283.                     /* The current block is large enough to fit
  284.                        data in including alignment */
  285.                     if ((void *) cur > heap_start) {
  286.                         /* There is a block before the current block.
  287.                            This previous block can be enlarged to compensate
  288.                            for the alignment excess */
  289.                         heap_block_foot_t *prev_foot =
  290.                             ((void *) cur) - sizeof(heap_block_foot_t);
  291.                        
  292.                         heap_block_head_t *prev_head =
  293.                             (heap_block_head_t *) (((void *) cur) - prev_foot->size);
  294.                        
  295.                         block_check(prev_head);
  296.                        
  297.                         size_t reduced_size = cur->size - excess;
  298.                         heap_block_head_t *next_head = ((void *) cur) + excess;
  299.                        
  300.                         if ((!prev_head->free) && (excess >= STRUCT_OVERHEAD)) {
  301.                             /* The previous block is not free and there is enough
  302.                                space to fill in a new free block between the previous
  303.                                and current block */
  304.                             block_init(cur, excess, true);
  305.                         } else {
  306.                             /* The previous block is free (thus there is no need to
  307.                                induce additional fragmentation to the heap) or the
  308.                                excess is small, thus just enlarge the previous block */
  309.                             block_init(prev_head, prev_head->size + excess, prev_head->free);
  310.                         }
  311.                        
  312.                         block_init(next_head, reduced_size, true);
  313.                         split_mark(next_head, real_size);
  314.                         result = aligned;
  315.                         cur = next_head;
  316.                     } else {
  317.                         /* The current block is the first block on the heap.
  318.                            We have to make sure that the alignment excess
  319.                            is large enough to fit a new free block just
  320.                            before the current block */
  321.                         while (excess < STRUCT_OVERHEAD) {
  322.                             aligned += falign;
  323.                             excess += falign;
  324.                         }
  325.                        
  326.                         /* Check for current block size again */
  327.                         if (cur->size >= real_size + excess) {
  328.                             size_t reduced_size = cur->size - excess;
  329.                             cur = (heap_block_head_t *) (heap_start + excess);
  330.                            
  331.                             block_init(heap_start, excess, true);
  332.                             block_init(cur, reduced_size, true);
  333.                             split_mark(cur, real_size);
  334.                             result = aligned;
  335.                         }
  336.                     }
  337.                 }
  338.             }
  339.         }
  340.        
  341.         /* Advance to the next block. */
  342.         cur = (heap_block_head_t *) (((void *) cur) + cur->size);
  343.     }
  344.    
  345.     if ((result == NULL) && (!grown)) {
  346.         if (grow_heap(real_size)) {
  347.             grown = true;
  348.             goto loop;
  349.         }
  350.     }
  351.    
  352.     return result;
  353. }
  354.  
  355. void *malloc(const size_t size)
  356. {
  357.     return malloc_internal(size, BASE_ALIGN);
  358. }
  359.  
  360. void *memalign(const size_t align, const size_t size)
  361. {
  362.     if (align == 0)
  363.         return NULL;
  364.    
  365.     size_t palign =
  366.         1 << (fnzb(max(sizeof(void *), align) - 1) + 1);
  367.    
  368.     return malloc_internal(size, palign);
  369. }
  370.  
  371. void *realloc(const void *addr, const size_t size)
  372. {
  373.     if (addr == NULL)
  374.         return malloc(size);
  375.    
  376.     /* Calculate the position of the header. */
  377.     heap_block_head_t *head =
  378.         (heap_block_head_t *) (addr - sizeof(heap_block_head_t));
  379.    
  380.     assert((void *) head >= heap_start);
  381.     assert((void *) head < heap_end);
  382.    
  383.     block_check(head);
  384.     assert(!head->free);
  385.    
  386.     void *ptr = NULL;
  387.     size_t real_size = GROSS_SIZE(ALIGN_UP(size, BASE_ALIGN));
  388.     size_t orig_size = head->size;
  389.    
  390.     if (orig_size > real_size) {
  391.         /* Shrink */
  392.         if (orig_size - real_size >= STRUCT_OVERHEAD) {
  393.             /* Split the original block to a full block
  394.                and a tailing free block */
  395.             block_init((void *) head, real_size, false);
  396.             block_init((void *) head + real_size,
  397.                 orig_size - real_size, true);
  398.             shrink_heap();
  399.         }
  400.        
  401.         ptr = ((void *) head) + sizeof(heap_block_head_t);
  402.     } else {
  403.         /* Look at the next block. If it is free and the size is
  404.            sufficient then merge the two. */
  405.         heap_block_head_t *next_head =
  406.             (heap_block_head_t *) (((void *) head) + head->size);
  407.        
  408.         if (((void *) next_head < heap_end) &&
  409.             (head->size + next_head->size >= real_size) &&
  410.             (next_head->free)) {
  411.             block_check(next_head);
  412.             block_init(head, head->size + next_head->size, false);
  413.             split_mark(head, ALIGN_UP(size, BASE_ALIGN));
  414.            
  415.             ptr = ((void *) head) + sizeof(heap_block_head_t);
  416.         } else {
  417.             ptr = malloc(size);
  418.             if (ptr != NULL) {
  419.                 memcpy(ptr, addr, NET_SIZE(orig_size));
  420.                 free(addr);
  421.             }
  422.         }
  423.     }
  424.    
  425.     return ptr;
  426. }
  427.  
  428. /** Free a memory block
  429.  *
  430.  * @param addr The address of the block.
  431.  */
  432. void free(const void *addr)
  433. {
  434.     /* Calculate the position of the header. */
  435.     heap_block_head_t *head
  436.         = (heap_block_head_t *) (addr - sizeof(heap_block_head_t));
  437.    
  438.     assert((void *) head >= heap_start);
  439.     assert((void *) head < heap_end);
  440.    
  441.     block_check(head);
  442.     assert(!head->free);
  443.    
  444.     /* Mark the block itself as free. */
  445.     head->free = true;
  446.    
  447.     /* Look at the next block. If it is free, merge the two. */
  448.     heap_block_head_t *next_head
  449.         = (heap_block_head_t *) (((void *) head) + head->size);
  450.    
  451.     if ((void *) next_head < heap_end) {
  452.         block_check(next_head);
  453.         if (next_head->free)
  454.             block_init(head, head->size + next_head->size, true);
  455.     }
  456.    
  457.     /* Look at the previous block. If it is free, merge the two. */
  458.     if ((void *) head > heap_start) {
  459.         heap_block_foot_t *prev_foot =
  460.             (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t));
  461.        
  462.         heap_block_head_t *prev_head =
  463.             (heap_block_head_t *) (((void *) head) - prev_foot->size);
  464.        
  465.         block_check(prev_head);
  466.        
  467.         if (prev_head->free)
  468.             block_init(prev_head, prev_head->size + head->size, true);
  469.     }
  470.    
  471.     shrink_heap();
  472. }
  473.  
  474. /** @}
  475.  */
  476.