Subversion Repositories HelenOS

Rev

Rev 4600 | 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, thus
  280.                    the previous block needs to be enlarged */
  281.                 size_t excess = (size_t) (aligned - addr);
  282.                
  283.                 if (cur->size >= real_size + excess) {
  284.                     if ((void *) cur > heap_start) {
  285.                         // TODO: This can be optimized further in case
  286.                         // of expanding a previous allocated block if the
  287.                         // excess is large enought to put another free
  288.                         // block in between
  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.                         cur = ((void *) cur) + excess;
  299.                        
  300.                         block_init(prev_head, prev_head->size + excess, prev_head->free);
  301.                         block_init(cur, reduced_size, true);
  302.                         split_mark(cur, real_size);
  303.                         result = aligned;
  304.                     } else {
  305.                         while (excess < STRUCT_OVERHEAD) {
  306.                             aligned += falign;
  307.                             excess += falign;
  308.                         }
  309.                        
  310.                         if (cur->size >= real_size + excess) {
  311.                             size_t reduced_size = cur->size - excess;
  312.                             cur = (heap_block_head_t *) (heap_start + excess);
  313.                            
  314.                             block_init(heap_start, excess, true);
  315.                             block_init(cur, reduced_size, true);
  316.                             split_mark(cur, real_size);
  317.                             result = aligned;
  318.                         }
  319.                     }
  320.                 }
  321.             }
  322.         }
  323.        
  324.         /* Advance to the next block. */
  325.         cur = (heap_block_head_t *) (((void *) cur) + cur->size);
  326.     }
  327.    
  328.     if ((result == NULL) && (!grown)) {
  329.         if (grow_heap(real_size)) {
  330.             grown = true;
  331.             goto loop;
  332.         }
  333.     }
  334.    
  335.     return result;
  336. }
  337.  
  338. void *malloc(const size_t size)
  339. {
  340.     return malloc_internal(size, BASE_ALIGN);
  341. }
  342.  
  343. void *memalign(const size_t align, const size_t size)
  344. {
  345.     if (align == 0)
  346.         return NULL;
  347.    
  348.     size_t palign =
  349.         1 << (fnzb(max(sizeof(void *), align) - 1) + 1);
  350.    
  351.     return malloc_internal(size, palign);
  352. }
  353.  
  354. void *realloc(const void *addr, const size_t size)
  355. {
  356.     if (addr == NULL)
  357.         return malloc(size);
  358.    
  359.     /* Calculate the position of the header. */
  360.     heap_block_head_t *head =
  361.         (heap_block_head_t *) (addr - sizeof(heap_block_head_t));
  362.    
  363.     assert((void *) head >= heap_start);
  364.     assert((void *) head < heap_end);
  365.    
  366.     block_check(head);
  367.     assert(!head->free);
  368.    
  369.     void *ptr = NULL;
  370.     size_t real_size = GROSS_SIZE(size);
  371.     size_t orig_size = head->size;
  372.    
  373.     if (orig_size > real_size) {
  374.         /* Shrink */
  375.         if (orig_size - real_size >= STRUCT_OVERHEAD) {
  376.             /* Split the original block to a full block
  377.                and a tailing free block */
  378.             block_init((void *) head, real_size, false);
  379.             block_init((void *) head + real_size,
  380.                 orig_size - real_size, true);
  381.             shrink_heap();
  382.         }
  383.        
  384.         ptr = ((void *) head) + sizeof(heap_block_head_t);
  385.     } else {
  386.         /* Look at the next block. If it is free and the size is
  387.            sufficient then merge the two. */
  388.         heap_block_head_t *next_head =
  389.             (heap_block_head_t *) (((void *) head) + head->size);
  390.        
  391.         if (((void *) next_head < heap_end)
  392.             && (head->size + next_head->size >= real_size)) {
  393.             block_check(next_head);
  394.             block_init(head, head->size + next_head->size, false);
  395.             split_mark(head, size);
  396.            
  397.             ptr = ((void *) head) + sizeof(heap_block_head_t);
  398.         } else {
  399.             ptr = malloc(size);
  400.             if (ptr != NULL) {
  401.                 memcpy(ptr, addr, NET_SIZE(orig_size));
  402.                 free(addr);
  403.             }
  404.         }
  405.     }
  406.    
  407.     return ptr;
  408. }
  409.  
  410. /** Free a memory block
  411.  *
  412.  * @param addr The address of the block.
  413.  */
  414. void free(const void *addr)
  415. {
  416.     /* Calculate the position of the header. */
  417.     heap_block_head_t *head
  418.         = (heap_block_head_t *) (addr - sizeof(heap_block_head_t));
  419.    
  420.     assert((void *) head >= heap_start);
  421.     assert((void *) head < heap_end);
  422.    
  423.     block_check(head);
  424.     assert(!head->free);
  425.    
  426.     /* Mark the block itself as free. */
  427.     head->free = true;
  428.    
  429.     /* Look at the next block. If it is free, merge the two. */
  430.     heap_block_head_t *next_head
  431.         = (heap_block_head_t *) (((void *) head) + head->size);
  432.    
  433.     if ((void *) next_head < heap_end) {
  434.         block_check(next_head);
  435.         if (next_head->free)
  436.             block_init(head, head->size + next_head->size, true);
  437.     }
  438.    
  439.     /* Look at the previous block. If it is free, merge the two. */
  440.     if ((void *) head > heap_start) {
  441.         heap_block_foot_t *prev_foot =
  442.             (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t));
  443.        
  444.         heap_block_head_t *prev_head =
  445.             (heap_block_head_t *) (((void *) head) - prev_foot->size);
  446.        
  447.         block_check(prev_head);
  448.        
  449.         if (prev_head->free)
  450.             block_init(prev_head, prev_head->size + head->size, true);
  451.     }
  452.    
  453.     shrink_heap();
  454. }
  455.  
  456. /** @}
  457.  */
  458.