Index: uspace/lib/c/generic/malloc.c =================================================================== --- uspace/lib/c/generic/malloc.c (revision 47b70062180b321b58ca43746901c748ff7a6b2d) +++ uspace/lib/c/generic/malloc.c (revision b7d960699b942f03e28e729f2b07c38e352f3588) @@ -47,33 +47,77 @@ #include "private/malloc.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) */ +/** Magic used in heap headers. */ +#define HEAP_BLOCK_HEAD_MAGIC UINT32_C(0xBEEF0101) + +/** Magic used in heap footers. */ +#define HEAP_BLOCK_FOOT_MAGIC UINT32_C(0xBEEF0202) + +/** Magic used in heap descriptor. */ +#define HEAP_AREA_MAGIC UINT32_C(0xBEEFCAFE) + +/** 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) +/** Overhead of each heap block. */ +#define STRUCT_OVERHEAD \ + (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t)) + +/** Calculate real size of a heap block. + * + * Add header and footer size. + * */ #define GROSS_SIZE(size) ((size) + STRUCT_OVERHEAD) -/** - * Calculate net size of a heap block (without header and footer) +/** Calculate net size of a heap block. + * + * Subtract header and footer size. + * */ #define NET_SIZE(size) ((size) - STRUCT_OVERHEAD) + +/** Get first block in heap area. + * + */ +#define AREA_FIRST_BLOCK(area) \ + (ALIGN_UP(((uintptr_t) (area)) + sizeof(heap_area_t), BASE_ALIGN)) + +/** Get footer in heap block. + * + */ +#define BLOCK_FOOT(head) \ + ((heap_block_foot_t *) \ + (((uintptr_t) head) + head->size - sizeof(heap_block_foot_t))) + +/** Heap area. + * + * The memory managed by the heap allocator is divided into + * multiple discontinuous heaps. Each heap is represented + * by a separate address space area which has this structure + * at its very beginning. + * + */ +typedef struct heap_area { + /** Start of the heap area (including this structure) + * + * Aligned on page boundary. + * + */ + void *start; + + /** End of the heap area (aligned on page boundary) */ + void *end; + + /** Next heap area */ + struct heap_area *next; + + /** A magic value */ + uint32_t magic; +} heap_area_t; /** Header of a heap block @@ -87,4 +131,7 @@ bool free; + /** Heap area this block belongs to */ + heap_area_t *area; + /* A magic value to detect overwrite of heap header */ uint32_t magic; @@ -102,25 +149,19 @@ } heap_block_foot_t; -/** Linker heap symbol */ -extern char _heap; +/** First heap area */ +static heap_area_t *first_heap_area = NULL; + +/** Last heap area */ +static heap_area_t *last_heap_area = NULL; + +/** Next heap block to examine (next fit algorithm) */ +static heap_block_head_t *next = NULL; /** Futex for thread-safe heap manipulation */ static futex_t malloc_futex = FUTEX_INITIALIZER; -/** 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. + * Fill in the structures related to a heap block. * Should be called only inside the critical section. * @@ -128,16 +169,18 @@ * @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) + * @param area Heap area the block belongs to. + * + */ +static void block_init(void *addr, size_t size, bool free, heap_area_t *area) { /* 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->area = area; head->magic = HEAP_BLOCK_HEAD_MAGIC; + + heap_block_foot_t *foot = BLOCK_FOOT(head); foot->size = size; @@ -160,6 +203,5 @@ assert(head->magic == HEAP_BLOCK_HEAD_MAGIC); - heap_block_foot_t *foot = - (heap_block_foot_t *) (addr + head->size - sizeof(heap_block_foot_t)); + heap_block_foot_t *foot = BLOCK_FOOT(head); assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC); @@ -167,49 +209,130 @@ } -/** Increase the heap area size - * - * Should be called only inside the critical section. - * - * @param size Number of bytes to grow the heap by. - * - */ -static bool grow_heap(size_t size) +/** Check a heap area structure + * + * @param addr Address of the heap area. + * + */ +static void area_check(void *addr) +{ + heap_area_t *area = (heap_area_t *) addr; + + assert(area->magic == HEAP_AREA_MAGIC); + assert(area->start < area->end); + assert(((uintptr_t) area->start % PAGE_SIZE) == 0); + assert(((uintptr_t) area->end % PAGE_SIZE) == 0); +} + +/** Create new heap area + * + * @param start Preffered starting address of the new area. + * @param size Size of the area. + * + */ +static bool area_create(size_t size) +{ + void *start = as_get_mappable_page(size); + if (start == NULL) + return false; + + /* Align the heap area on page boundary */ + void *astart = (void *) ALIGN_UP((uintptr_t) start, PAGE_SIZE); + size_t asize = ALIGN_UP(size, PAGE_SIZE); + + astart = as_area_create(astart, asize, AS_AREA_WRITE | AS_AREA_READ); + if (astart == (void *) -1) + return false; + + heap_area_t *area = (heap_area_t *) astart; + + area->start = astart; + area->end = (void *) + ALIGN_DOWN((uintptr_t) astart + asize, BASE_ALIGN); + area->next = NULL; + area->magic = HEAP_AREA_MAGIC; + + void *block = (void *) AREA_FIRST_BLOCK(area); + size_t bsize = (size_t) (area->end - block); + + block_init(block, bsize, true, area); + + if (last_heap_area == NULL) { + first_heap_area = area; + last_heap_area = area; + } else { + last_heap_area->next = area; + last_heap_area = area; + } + + return true; +} + +/** Try to enlarge a heap area + * + * @param area Heap area to grow. + * @param size Gross size of item to allocate (bytes). + * + */ +static bool area_grow(heap_area_t *area, size_t size) { if (size == 0) + return true; + + area_check(area); + + size_t asize = ALIGN_UP((size_t) (area->end - area->start) + size, + PAGE_SIZE); + + /* New heap area size */ + void *end = (void *) + ALIGN_DOWN((uintptr_t) area->start + asize, BASE_ALIGN); + + /* Check for overflow */ + if (end < area->start) return false; - - if ((heap_start + size < heap_start) || (heap_end + size < heap_end)) + + /* Resize the address space area */ + int ret = as_area_resize(area->start, asize, 0); + if (ret != EOK) 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; + /* Add new free block */ + block_init(area->end, (size_t) (end - area->end), true, area); + + /* Update heap area parameters */ + area->end = end; + + return true; +} + +/** Try to enlarge any of the heap areas + * + * @param size Gross size of item to allocate (bytes). + * + */ +static bool heap_grow(size_t size) +{ + if (size == 0) return true; - } - - return false; -} - -/** Decrease the heap area - * - * Should be called only inside the critical section. - * - * @param size Number of bytes to shrink the heap by. - * - */ -static void shrink_heap(void) -{ - // TODO + + /* First try to enlarge some existing area */ + heap_area_t *area; + for (area = first_heap_area; area != NULL; area = area->next) { + if (area_grow(area, size)) + return true; + } + + /* Eventually try to create a new area */ + return area_create(AREA_FIRST_BLOCK(size)); +} + +/** Try to shrink heap space + * + * In all cases the next pointer is reset. + * + */ +static void heap_shrink(void) +{ + next = NULL; } @@ -223,33 +346,6 @@ void __malloc_init(void) { - if (!as_area_create((void *) &_heap, PAGE_SIZE, - AS_AREA_WRITE | AS_AREA_READ)) + if (!area_create(PAGE_SIZE)) abort(); - - 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); -} - -/** Get maximum heap address - * - */ -uintptr_t get_max_heap_addr(void) -{ - futex_down(&malloc_futex); - - if (max_heap_size == (size_t) -1) - max_heap_size = - max((size_t) (heap_end - heap_start), MAX_HEAP_SIZE); - - uintptr_t max_heap_addr = (uintptr_t) heap_start + max_heap_size; - - futex_up(&malloc_futex); - - return max_heap_addr; } @@ -273,6 +369,6 @@ /* Block big enough -> split. */ void *next = ((void *) cur) + size; - block_init(next, cur->size - size, true); - block_init(cur, size, false); + block_init(next, cur->size - size, true, cur->area); + block_init(cur, size, false, cur->area); } else { /* Block too small -> use as is. */ @@ -281,43 +377,53 @@ } -/** Allocate a memory block +/** Allocate memory from heap area starting from given block * * Should be called only inside the critical section. - * - * @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)) { + * As a side effect this function also sets the current + * pointer on successful allocation. + * + * @param area Heap area where to allocate from. + * @param first_block Starting heap block. + * @param final_block Heap block where to finish the search + * (may be NULL). + * @param real_size Gross number of bytes to allocate. + * @param falign Physical alignment of the block. + * + * @return Address of the allocated block or NULL on not enough memory. + * + */ +static void *malloc_area(heap_area_t *area, heap_block_head_t *first_block, + heap_block_head_t *final_block, size_t real_size, size_t falign) +{ + area_check((void *) area); + assert((void *) first_block >= (void *) AREA_FIRST_BLOCK(area)); + assert((void *) first_block < area->end); + + heap_block_head_t *cur; + for (cur = first_block; (void *) cur < area->end; + cur = (heap_block_head_t *) (((void *) cur) + cur->size)) { block_check(cur); + + /* Finish searching on the final block */ + if ((final_block != NULL) && (cur == final_block)) + break; /* 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); + /* + * We have found a suitable block. + * Check for alignment properties. + */ + void *addr = (void *) + ((uintptr_t) cur + sizeof(heap_block_head_t)); + void *aligned = (void *) + ALIGN_UP((uintptr_t) addr, falign); if (addr == aligned) { /* Exact block start including alignment. */ split_mark(cur, real_size); - result = addr; + + next = cur; + return addr; } else { /* Block start has to be aligned */ @@ -325,15 +431,19 @@ if (cur->size >= real_size + excess) { - /* The current block is large enough to fit - data in including alignment */ - if ((void *) cur > heap_start) { - /* There is a block before the current block. - This previous block can be enlarged to compensate - for the alignment excess */ - heap_block_foot_t *prev_foot = - ((void *) cur) - sizeof(heap_block_foot_t); + /* + * The current block is large enough to fit + * data in (including alignment). + */ + if ((void *) cur > (void *) AREA_FIRST_BLOCK(area)) { + /* + * There is a block before the current block. + * This previous block can be enlarged to + * compensate for the alignment excess. + */ + heap_block_foot_t *prev_foot = (heap_block_foot_t *) + ((void *) cur - sizeof(heap_block_foot_t)); - heap_block_head_t *prev_head = - (heap_block_head_t *) (((void *) cur) - prev_foot->size); + heap_block_head_t *prev_head = (heap_block_head_t *) + ((void *) cur - prev_foot->size); block_check(prev_head); @@ -342,25 +452,38 @@ heap_block_head_t *next_head = ((void *) cur) + excess; - if ((!prev_head->free) && (excess >= STRUCT_OVERHEAD)) { - /* The previous block is not free and there is enough - space to fill in a new free block between the previous - and current block */ - block_init(cur, excess, true); + if ((!prev_head->free) && + (excess >= STRUCT_OVERHEAD)) { + /* + * The previous block is not free and there + * is enough free space left to fill in + * a new free block between the previous + * and current block. + */ + block_init(cur, excess, true, area); } else { - /* The previous block is free (thus there is no need to - induce additional fragmentation to the heap) or the - excess is small, thus just enlarge the previous block */ - block_init(prev_head, prev_head->size + excess, prev_head->free); + /* + * The previous block is free (thus there + * is no need to induce additional + * fragmentation to the heap) or the + * excess is small. Therefore just enlarge + * the previous block. + */ + block_init(prev_head, prev_head->size + excess, + prev_head->free, area); } - block_init(next_head, reduced_size, true); + block_init(next_head, reduced_size, true, area); split_mark(next_head, real_size); - result = aligned; - cur = next_head; + + next = next_head; + return aligned; } else { - /* The current block is the first block on the heap. - We have to make sure that the alignment excess - is large enough to fit a new free block just - before the current block */ + /* + * The current block is the first block + * in the heap area. We have to make sure + * that the alignment excess is large enough + * to fit a new free block just before the + * current block. + */ while (excess < STRUCT_OVERHEAD) { aligned += falign; @@ -371,10 +494,14 @@ if (cur->size >= real_size + excess) { size_t reduced_size = cur->size - excess; - cur = (heap_block_head_t *) (heap_start + excess); + cur = (heap_block_head_t *) + (AREA_FIRST_BLOCK(area) + excess); - block_init(heap_start, excess, true); - block_init(cur, reduced_size, true); + block_init((void *) AREA_FIRST_BLOCK(area), excess, + true, area); + block_init(cur, reduced_size, true, area); split_mark(cur, real_size); - result = aligned; + + next = cur; + return aligned; } } @@ -382,17 +509,67 @@ } } - - /* 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; + } + + return NULL; +} + +/** Allocate a memory block + * + * Should be called only inside the critical section. + * + * @param size The size of the block to allocate. + * @param align Memory address alignment. + * + * @return Address of the allocated block or NULL on not enough memory. + * + */ +static void *malloc_internal(const size_t size, const size_t align) +{ + assert(first_heap_area != NULL); + + if (align == 0) + return NULL; + + size_t falign = lcm(align, BASE_ALIGN); + size_t real_size = GROSS_SIZE(ALIGN_UP(size, falign)); + + bool retry = false; + heap_block_head_t *split; + +loop: + + /* Try the next fit approach */ + split = next; + + if (split != NULL) { + void *addr = malloc_area(split->area, split, NULL, real_size, + falign); + + if (addr != NULL) + return addr; + } + + /* Search the entire heap */ + heap_area_t *area; + for (area = first_heap_area; area != NULL; area = area->next) { + heap_block_head_t *first = (heap_block_head_t *) + AREA_FIRST_BLOCK(area); + + void *addr = malloc_area(area, first, split, real_size, + falign); + + if (addr != NULL) + return addr; + } + + if (!retry) { + /* Try to grow the heap space */ + if (heap_grow(real_size)) { + retry = true; goto loop; } } - return result; + return NULL; } @@ -473,9 +650,12 @@ (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); + + heap_area_t *area = head->area; + + area_check(area); + assert((void *) head >= (void *) AREA_FIRST_BLOCK(area)); + assert((void *) head < area->end); void *ptr = NULL; @@ -487,29 +667,34 @@ /* Shrink */ if (orig_size - real_size >= STRUCT_OVERHEAD) { - /* Split the original block to a full block - and a trailing free block */ - block_init((void *) head, real_size, false); + /* + * Split the original block to a full block + * and a trailing free block. + */ + block_init((void *) head, real_size, false, area); block_init((void *) head + real_size, - orig_size - real_size, true); - shrink_heap(); + orig_size - real_size, true, area); + heap_shrink(); } 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. Otherwise just allocate - a new block, copy the original data into it and - free the original block. */ + /* + * Look at the next block. If it is free and the size is + * sufficient then merge the two. Otherwise just allocate + * a new block, copy the original data into it and + * free the original block. + */ heap_block_head_t *next_head = (heap_block_head_t *) (((void *) head) + head->size); - if (((void *) next_head < heap_end) && + if (((void *) next_head < area->end) && (head->size + next_head->size >= real_size) && (next_head->free)) { block_check(next_head); - block_init(head, head->size + next_head->size, false); + block_init(head, head->size + next_head->size, false, area); split_mark(head, real_size); ptr = ((void *) head) + sizeof(heap_block_head_t); + next = NULL; } else reloc = true; @@ -542,9 +727,12 @@ = (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); + + heap_area_t *area = head->area; + + area_check(area); + assert((void *) head >= (void *) AREA_FIRST_BLOCK(area)); + assert((void *) head < area->end); /* Mark the block itself as free. */ @@ -555,12 +743,12 @@ = (heap_block_head_t *) (((void *) head) + head->size); - if ((void *) next_head < heap_end) { + if ((void *) next_head < area->end) { block_check(next_head); if (next_head->free) - block_init(head, head->size + next_head->size, true); + block_init(head, head->size + next_head->size, true, area); } /* Look at the previous block. If it is free, merge the two. */ - if ((void *) head > heap_start) { + if ((void *) head > (void *) AREA_FIRST_BLOCK(area)) { heap_block_foot_t *prev_foot = (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t)); @@ -572,8 +760,9 @@ if (prev_head->free) - block_init(prev_head, prev_head->size + head->size, true); - } - - shrink_heap(); + block_init(prev_head, prev_head->size + head->size, true, + area); + } + + heap_shrink(); futex_up(&malloc_futex);