| 0,0 → 1,457 |
|---|
| /* |
| * Copyright (c) 2009 Martin Decky |
| * Copyright (c) 2009 Petr Tuma |
| * 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. |
| */ |
| |
| /** @addtogroup libc |
| * @{ |
| */ |
| /** @file |
| */ |
| |
| #include <malloc.h> |
| #include <bool.h> |
| #include <as.h> |
| #include <align.h> |
| #include <macros.h> |
| #include <assert.h> |
| #include <errno.h> |
| #include <bitops.h> |
| #include <mem.h> |
| #include <adt/gcdlcm.h> |
| |
| /* Magic used in heap headers. */ |
| #define HEAP_BLOCK_HEAD_MAGIC 0xBEEF0101 |
| |
| /* Magic used in heap footers. */ |
| #define HEAP_BLOCK_FOOT_MAGIC 0xBEEF0202 |
| |
| /** Allocation alignment (this also covers the alignment of fields |
| in the heap header and footer) */ |
| #define BASE_ALIGN 16 |
| |
| /** |
| * Either 4 * 256M on 32-bit architecures or 16 * 256M on 64-bit architectures |
| */ |
| #define MAX_HEAP_SIZE (sizeof(uintptr_t) << 28) |
| |
| /** |
| * |
| */ |
| #define STRUCT_OVERHEAD (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t)) |
| |
| /** |
| * Calculate real size of a heap block (with header and footer) |
| */ |
| #define GROSS_SIZE(size) ((size) + STRUCT_OVERHEAD) |
| |
| /** |
| * Calculate net size of a heap block (without header and footer) |
| */ |
| #define NET_SIZE(size) ((size) - STRUCT_OVERHEAD) |
| |
| |
| /** Header of a heap block |
| * |
| */ |
| typedef struct { |
| /* Size of the block (including header and footer) */ |
| size_t size; |
| |
| /* Indication of a free block */ |
| bool free; |
| |
| /* A magic value to detect overwrite of heap header */ |
| uint32_t magic; |
| } heap_block_head_t; |
| |
| /** Footer of a heap block |
| * |
| */ |
| typedef struct { |
| /* Size of the block (including header and footer) */ |
| size_t size; |
| |
| /* A magic value to detect overwrite of heap footer */ |
| uint32_t magic; |
| } heap_block_foot_t; |
| |
| /** Linker heap symbol */ |
| extern char _heap; |
| |
| /** Address of heap start */ |
| static void *heap_start = 0; |
| |
| /** Address of heap end */ |
| static void *heap_end = 0; |
| |
| /** Maximum heap size */ |
| static size_t max_heap_size = (size_t) -1; |
| |
| /** Current number of pages of heap area */ |
| static size_t heap_pages = 0; |
| |
| /** Initialize a heap block |
| * |
| * Fills in the structures related to a heap block. |
| * |
| * @param addr Address of the block. |
| * @param size Size of the block including the header and the footer. |
| * @param free Indication of a free block. |
| * |
| */ |
| static void block_init(void *addr, size_t size, bool free) |
| { |
| /* Calculate the position of the header and the footer */ |
| heap_block_head_t *head = (heap_block_head_t *) addr; |
| heap_block_foot_t *foot = |
| (heap_block_foot_t *) (addr + size - sizeof(heap_block_foot_t)); |
| |
| head->size = size; |
| head->free = free; |
| head->magic = HEAP_BLOCK_HEAD_MAGIC; |
| |
| foot->size = size; |
| foot->magic = HEAP_BLOCK_FOOT_MAGIC; |
| } |
| |
| /** Check a heap block |
| * |
| * Verifies that the structures related to a heap block still contain |
| * the magic constants. This helps detect heap corruption early on. |
| * |
| * @param addr Address of the block. |
| * |
| */ |
| static void block_check(void *addr) |
| { |
| heap_block_head_t *head = (heap_block_head_t *) addr; |
| |
| assert(head->magic == HEAP_BLOCK_HEAD_MAGIC); |
| |
| heap_block_foot_t *foot = |
| (heap_block_foot_t *) (addr + head->size - sizeof(heap_block_foot_t)); |
| |
| assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC); |
| assert(head->size == foot->size); |
| } |
| |
| static bool grow_heap(size_t size) |
| { |
| if (size == 0) |
| return false; |
| |
| size_t heap_size = (size_t) (heap_end - heap_start); |
| |
| if ((max_heap_size != (size_t) -1) && (heap_size + size > max_heap_size)) |
| return false; |
| |
| size_t pages = (size - 1) / PAGE_SIZE + 1; |
| |
| if (as_area_resize((void *) &_heap, (heap_pages + pages) * PAGE_SIZE, 0) |
| == EOK) { |
| void *end = (void *) ALIGN_DOWN(((uintptr_t) &_heap) + |
| (heap_pages + pages) * PAGE_SIZE, BASE_ALIGN); |
| block_init(heap_end, end - heap_end, true); |
| heap_pages += pages; |
| heap_end = end; |
| return true; |
| } |
| |
| return false; |
| } |
| |
| static void shrink_heap(void) |
| { |
| // TODO |
| } |
| |
| /** Initialize the heap allocator |
| * |
| * Finds how much physical memory we have and creates |
| * the heap management structures that mark the whole |
| * physical memory as a single free block. |
| * |
| */ |
| void __heap_init(void) |
| { |
| if (as_area_create((void *) &_heap, PAGE_SIZE, |
| AS_AREA_WRITE | AS_AREA_READ)) { |
| heap_pages = 1; |
| heap_start = (void *) ALIGN_UP((uintptr_t) &_heap, BASE_ALIGN); |
| heap_end = |
| (void *) ALIGN_DOWN(((uintptr_t) &_heap) + PAGE_SIZE, BASE_ALIGN); |
| |
| /* Make the entire area one large block. */ |
| block_init(heap_start, heap_end - heap_start, true); |
| } |
| } |
| |
| uintptr_t get_max_heap_addr(void) |
| { |
| if (max_heap_size == (size_t) -1) |
| max_heap_size = |
| max((size_t) (heap_end - heap_start), MAX_HEAP_SIZE); |
| |
| return ((uintptr_t) heap_start + max_heap_size); |
| } |
| |
| static void split_mark(heap_block_head_t *cur, const size_t size) |
| { |
| assert(cur->size >= size); |
| |
| /* See if we should split the block. */ |
| size_t split_limit = GROSS_SIZE(size); |
| |
| if (cur->size > split_limit) { |
| /* Block big enough -> split. */ |
| void *next = ((void *) cur) + size; |
| block_init(next, cur->size - size, true); |
| block_init(cur, size, false); |
| } else { |
| /* Block too small -> use as is. */ |
| cur->free = false; |
| } |
| } |
| |
| /** Allocate a memory block |
| * |
| * @param size The size of the block to allocate. |
| * @param align Memory address alignment. |
| * |
| * @return the address of the block or NULL when not enough memory. |
| * |
| */ |
| static void *malloc_internal(const size_t size, const size_t align) |
| { |
| if (align == 0) |
| return NULL; |
| |
| size_t falign = lcm(align, BASE_ALIGN); |
| size_t real_size = GROSS_SIZE(ALIGN_UP(size, falign)); |
| |
| bool grown = false; |
| void *result; |
| |
| loop: |
| result = NULL; |
| heap_block_head_t *cur = (heap_block_head_t *) heap_start; |
| |
| while ((result == NULL) && ((void *) cur < heap_end)) { |
| block_check(cur); |
| |
| /* Try to find a block that is free and large enough. */ |
| if ((cur->free) && (cur->size >= real_size)) { |
| /* We have found a suitable block. |
| Check for alignment properties. */ |
| void *addr = ((void *) cur) + sizeof(heap_block_head_t); |
| void *aligned = (void *) ALIGN_UP(addr, falign); |
| |
| if (addr == aligned) { |
| /* Exact block start including alignment. */ |
| split_mark(cur, real_size); |
| result = addr; |
| } else { |
| /* Block start has to be aligned, thus |
| the previous block needs to be enlarged */ |
| size_t excess = (size_t) (aligned - addr); |
| |
| if (cur->size >= real_size + excess) { |
| if ((void *) cur > heap_start) { |
| // TODO: This can be optimized further in case |
| // of expanding a previous allocated block if the |
| // excess is large enought to put another free |
| // block in between |
| heap_block_foot_t *prev_foot = |
| ((void *) cur) - sizeof(heap_block_foot_t); |
| |
| heap_block_head_t *prev_head = |
| (heap_block_head_t *) (((void *) cur) - prev_foot->size); |
| |
| block_check(prev_head); |
| |
| size_t reduced_size = cur->size - excess; |
| cur = ((void *) cur) + excess; |
| |
| block_init(prev_head, prev_head->size + excess, prev_head->free); |
| block_init(cur, reduced_size, true); |
| split_mark(cur, real_size); |
| result = aligned; |
| } else { |
| while (excess < STRUCT_OVERHEAD) { |
| aligned += falign; |
| excess += falign; |
| } |
| |
| if (cur->size >= real_size + excess) { |
| size_t reduced_size = cur->size - excess; |
| cur = (heap_block_head_t *) (heap_start + excess); |
| |
| block_init(heap_start, excess, true); |
| block_init(cur, reduced_size, true); |
| split_mark(cur, real_size); |
| result = aligned; |
| } |
| } |
| } |
| } |
| } |
| |
| /* Advance to the next block. */ |
| cur = (heap_block_head_t *) (((void *) cur) + cur->size); |
| } |
| |
| if ((result == NULL) && (!grown)) { |
| if (grow_heap(real_size)) { |
| grown = true; |
| goto loop; |
| } |
| } |
| |
| return result; |
| } |
| |
| void *malloc(const size_t size) |
| { |
| return malloc_internal(size, BASE_ALIGN); |
| } |
| |
| void *memalign(const size_t align, const size_t size) |
| { |
| if (align == 0) |
| return NULL; |
| |
| size_t palign = |
| 1 << (fnzb(max(sizeof(void *), align) - 1) + 1); |
| |
| return malloc_internal(size, palign); |
| } |
| |
| void *realloc(const void *addr, const size_t size) |
| { |
| if (addr == NULL) |
| return malloc(size); |
| |
| /* Calculate the position of the header. */ |
| heap_block_head_t *head = |
| (heap_block_head_t *) (addr - sizeof(heap_block_head_t)); |
| |
| assert((void *) head >= heap_start); |
| assert((void *) head < heap_end); |
| |
| block_check(head); |
| assert(!head->free); |
| |
| void *ptr = NULL; |
| size_t real_size = GROSS_SIZE(size); |
| size_t orig_size = head->size; |
| |
| if (orig_size > real_size) { |
| /* Shrink */ |
| if (orig_size - real_size >= STRUCT_OVERHEAD) { |
| /* Split the original block to a full block |
| and a tailing free block */ |
| block_init((void *) head, real_size, false); |
| block_init((void *) head + real_size, |
| orig_size - real_size, true); |
| shrink_heap(); |
| } |
| |
| ptr = ((void *) head) + sizeof(heap_block_head_t); |
| } else { |
| /* Look at the next block. If it is free and the size is |
| sufficient then merge the two. */ |
| heap_block_head_t *next_head = |
| (heap_block_head_t *) (((void *) head) + head->size); |
| |
| if (((void *) next_head < heap_end) |
| && (head->size + next_head->size >= real_size)) { |
| block_check(next_head); |
| block_init(head, head->size + next_head->size, false); |
| split_mark(head, size); |
| |
| ptr = ((void *) head) + sizeof(heap_block_head_t); |
| } else { |
| ptr = malloc(size); |
| if (ptr != NULL) { |
| memcpy(ptr, addr, NET_SIZE(orig_size)); |
| free(addr); |
| } |
| } |
| } |
| |
| return ptr; |
| } |
| |
| /** Free a memory block |
| * |
| * @param addr The address of the block. |
| */ |
| void free(const void *addr) |
| { |
| /* Calculate the position of the header. */ |
| heap_block_head_t *head |
| = (heap_block_head_t *) (addr - sizeof(heap_block_head_t)); |
| |
| assert((void *) head >= heap_start); |
| assert((void *) head < heap_end); |
| |
| block_check(head); |
| assert(!head->free); |
| |
| /* Mark the block itself as free. */ |
| head->free = true; |
| |
| /* Look at the next block. If it is free, merge the two. */ |
| heap_block_head_t *next_head |
| = (heap_block_head_t *) (((void *) head) + head->size); |
| |
| if ((void *) next_head < heap_end) { |
| block_check(next_head); |
| if (next_head->free) |
| block_init(head, head->size + next_head->size, true); |
| } |
| |
| /* Look at the previous block. If it is free, merge the two. */ |
| if ((void *) head > heap_start) { |
| heap_block_foot_t *prev_foot = |
| (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t)); |
| |
| heap_block_head_t *prev_head = |
| (heap_block_head_t *) (((void *) head) - prev_foot->size); |
| |
| block_check(prev_head); |
| |
| if (prev_head->free) |
| block_init(prev_head, prev_head->size + head->size, true); |
| } |
| |
| shrink_heap(); |
| } |
| |
| /** @} |
| */ |