malloc.c

Go to the documentation of this file.

/*
 * 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.
 */

#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 <futex.h>
#include <stdlib.h>
#include <adt/gcdlcm.h>
#include "private/malloc.h"

#define HEAP_BLOCK_HEAD_MAGIC  UINT32_C(0xBEEF0101)

#define HEAP_BLOCK_FOOT_MAGIC  UINT32_C(0xBEEF0202)

#define HEAP_AREA_MAGIC  UINT32_C(0xBEEFCAFE)

#define BASE_ALIGN  16

#define SHRINK_GRANULARITY  (64 * PAGE_SIZE)

#define STRUCT_OVERHEAD \
        (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t))

#define AREA_OVERHEAD(size) \
        (ALIGN_UP(size + sizeof(heap_area_t), BASE_ALIGN))

#define GROSS_SIZE(size)  ((size) + STRUCT_OVERHEAD)

#define NET_SIZE(size)  ((size) - STRUCT_OVERHEAD)

#define AREA_FIRST_BLOCK_HEAD(area) \
        (ALIGN_UP(((uintptr_t) (area)) + sizeof(heap_area_t), BASE_ALIGN))

#define AREA_LAST_BLOCK_FOOT(area) \
        (((uintptr_t) (area)->end) - sizeof(heap_block_foot_t))

#define BLOCK_HEAD(foot) \
        ((heap_block_head_t *) \
            (((uintptr_t) (foot)) + sizeof(heap_block_foot_t) - (foot)->size))

#define BLOCK_FOOT(head) \
        ((heap_block_foot_t *) \
            (((uintptr_t) (head)) + (head)->size - sizeof(heap_block_foot_t)))

typedef struct heap_area {
        void *start;
        
        void *end;
        
        struct heap_area *prev;
        
        struct heap_area *next;
        
        uint32_t magic;
} heap_area_t;

typedef struct {
        /* Size of the block (including header and footer) */
        size_t size;
        
        /* Indication of a free block */
        bool free;
        
        heap_area_t *area;
        
        /* A magic value to detect overwrite of heap header */
        uint32_t magic;
} heap_block_head_t;

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;

static heap_area_t *first_heap_area = NULL;

static heap_area_t *last_heap_area = NULL;

static heap_block_head_t *next_fit = NULL;

static futex_t malloc_futex = FUTEX_INITIALIZER;

#ifndef NDEBUG

#define malloc_assert(expr) \
        do { \
                if (!(expr)) {\
                        futex_up(&malloc_futex); \
                        assert_abort(#expr, __FILE__, __LINE__); \
                } \
        } while (0)

#else /* NDEBUG */

#define malloc_assert(expr)

#endif /* NDEBUG */

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;
        
        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;
        foot->magic = HEAP_BLOCK_FOOT_MAGIC;
}

static void block_check(void *addr)
{
        heap_block_head_t *head = (heap_block_head_t *) addr;
        
        malloc_assert(head->magic == HEAP_BLOCK_HEAD_MAGIC);
        
        heap_block_foot_t *foot = BLOCK_FOOT(head);
        
        malloc_assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC);
        malloc_assert(head->size == foot->size);
}

static void area_check(void *addr)
{
        heap_area_t *area = (heap_area_t *) addr;
        
        malloc_assert(area->magic == HEAP_AREA_MAGIC);
        malloc_assert(addr == area->start);
        malloc_assert(area->start < area->end);
        malloc_assert(((uintptr_t) area->start % PAGE_SIZE) == 0);
        malloc_assert(((uintptr_t) area->end % PAGE_SIZE) == 0);
}

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 | AS_AREA_CACHEABLE);
        if (astart == (void *) -1)
                return false;
        
        heap_area_t *area = (heap_area_t *) astart;
        
        area->start = astart;
        area->end = (void *) ((uintptr_t) astart + asize);
        area->prev = NULL;
        area->next = NULL;
        area->magic = HEAP_AREA_MAGIC;
        
        void *block = (void *) AREA_FIRST_BLOCK_HEAD(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 {
                area->prev = last_heap_area;
                last_heap_area->next = area;
                last_heap_area = area;
        }
        
        return true;
}

static bool area_grow(heap_area_t *area, size_t size)
{
        if (size == 0)
                return true;
        
        area_check(area);
        
        /* New heap area size */
        size_t gross_size = (size_t) (area->end - area->start) + size;
        size_t asize = ALIGN_UP(gross_size, PAGE_SIZE);
        void *end = (void *) ((uintptr_t) area->start + asize);
        
        /* Check for overflow */
        if (end < area->start)
                return false;
        
        /* Resize the address space area */
        int ret = as_area_resize(area->start, asize, 0);
        if (ret != EOK)
                return false;
        
        /* Add new free block */
        size_t net_size = (size_t) (end - area->end);
        if (net_size > 0)
                block_init(area->end, net_size, true, area);
        
        /* Update heap area parameters */
        area->end = end;
        
        return true;
}

static bool heap_grow(size_t size)
{
        if (size == 0)
                return true;
        
        /* First try to enlarge some existing area */
        for (heap_area_t *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_OVERHEAD(size));
}

static void heap_shrink(heap_area_t *area)
{
        area_check(area);
        
        heap_block_foot_t *last_foot =
            (heap_block_foot_t *) AREA_LAST_BLOCK_FOOT(area);
        heap_block_head_t *last_head = BLOCK_HEAD(last_foot);
        
        block_check((void *) last_head);
        malloc_assert(last_head->area == area);
        
        if (last_head->free) {
                /*
                 * The last block of the heap area is
                 * unused. The area might be potentially
                 * shrunk.
                 */
                
                heap_block_head_t *first_head =
                    (heap_block_head_t *) AREA_FIRST_BLOCK_HEAD(area);
                
                block_check((void *) first_head);
                malloc_assert(first_head->area == area);
                
                size_t shrink_size = ALIGN_DOWN(last_head->size, PAGE_SIZE);
                
                if (first_head == last_head) {
                        /*
                         * The entire heap area consists of a single
                         * free heap block. This means we can get rid
                         * of it entirely.
                         */
                        
                        heap_area_t *prev = area->prev;
                        heap_area_t *next = area->next;
                        
                        if (prev != NULL) {
                                area_check(prev);
                                prev->next = next;
                        } else
                                first_heap_area = next;
                        
                        if (next != NULL) {
                                area_check(next);
                                next->prev = prev;
                        } else
                                last_heap_area = prev;
                        
                        as_area_destroy(area->start);
                } else if (shrink_size >= SHRINK_GRANULARITY) {
                        /*
                         * Make sure that we always shrink the area
                         * by a multiple of page size and update
                         * the block layout accordingly.
                         */
                        
                        size_t asize = (size_t) (area->end - area->start) - shrink_size;
                        void *end = (void *) ((uintptr_t) area->start + asize);
                        
                        /* Resize the address space area */
                        int ret = as_area_resize(area->start, asize, 0);
                        if (ret != EOK)
                                abort();
                        
                        /* Update heap area parameters */
                        area->end = end;
                        size_t excess = ((size_t) area->end) - ((size_t) last_head);
                        
                        if (excess > 0) {
                                if (excess >= STRUCT_OVERHEAD) {
                                        /*
                                         * The previous block cannot be free and there
                                         * is enough free space left in the area to
                                         * create a new free block.
                                         */
                                        block_init((void *) last_head, excess, true, area);
                                } else {
                                        /*
                                         * The excess is small. Therefore just enlarge
                                         * the previous block.
                                         */
                                        heap_block_foot_t *prev_foot = (heap_block_foot_t *)
                                            (((uintptr_t) last_head) - sizeof(heap_block_foot_t));
                                        heap_block_head_t *prev_head = BLOCK_HEAD(prev_foot);
                                        
                                        block_check((void *) prev_head);
                                        
                                        block_init(prev_head, prev_head->size + excess,
                                            prev_head->free, area);
                                }
                        }
                }
        }
        
        next_fit = NULL;
}

void __malloc_init(void)
{
        if (!area_create(PAGE_SIZE))
                abort();
}

static void split_mark(heap_block_head_t *cur, const size_t size)
{
        malloc_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, cur->area);
                block_init(cur, size, false, cur->area);
        } else {
                /* Block too small -> use as is. */
                cur->free = false;
        }
}

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);
        malloc_assert((void *) first_block >= (void *) AREA_FIRST_BLOCK_HEAD(area));
        malloc_assert((void *) first_block < area->end);
        
        for (heap_block_head_t *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 *)
                            ((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);
                                
                                next_fit = cur;
                                return addr;
                        } else {
                                /* Block start has to be aligned */
                                size_t excess = (size_t) (aligned - addr);
                                
                                if (cur->size >= real_size + excess) {
                                        /*
                                         * The current block is large enough to fit
                                         * data in (including alignment).
                                         */
                                        if ((void *) cur > (void *) AREA_FIRST_BLOCK_HEAD(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);
                                                
                                                block_check(prev_head);
                                                
                                                size_t reduced_size = cur->size - excess;
                                                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 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. 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, area);
                                                split_mark(next_head, real_size);
                                                
                                                next_fit = next_head;
                                                return aligned;
                                        } else {
                                                /*
                                                 * 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;
                                                        excess += falign;
                                                }
                                                
                                                /* Check for current block size again */
                                                if (cur->size >= real_size + excess) {
                                                        size_t reduced_size = cur->size - excess;
                                                        cur = (heap_block_head_t *)
                                                            (AREA_FIRST_BLOCK_HEAD(area) + excess);
                                                        
                                                        block_init((void *) AREA_FIRST_BLOCK_HEAD(area),
                                                            excess, true, area);
                                                        block_init(cur, reduced_size, true, area);
                                                        split_mark(cur, real_size);
                                                        
                                                        next_fit = cur;
                                                        return aligned;
                                                }
                                        }
                                }
                        }
                }
        }
        
        return NULL;
}

static void *malloc_internal(const size_t size, const size_t align)
{
        malloc_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_fit;
        
        if (split != NULL) {
                void *addr = malloc_area(split->area, split, NULL, real_size,
                    falign);
                
                if (addr != NULL)
                        return addr;
        }
        
        /* Search the entire heap */
        for (heap_area_t *area = first_heap_area; area != NULL;
            area = area->next) {
                heap_block_head_t *first = (heap_block_head_t *)
                    AREA_FIRST_BLOCK_HEAD(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 NULL;
}

void *calloc(const size_t nmemb, const size_t size)
{
        void *block = malloc(nmemb * size);
        if (block == NULL)
                return NULL;
        
        memset(block, 0, nmemb * size);
        return block;
}

void *malloc(const size_t size)
{
        futex_down(&malloc_futex);
        void *block = malloc_internal(size, BASE_ALIGN);
        futex_up(&malloc_futex);
        
        return block;
}

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);
        
        futex_down(&malloc_futex);
        void *block = malloc_internal(size, palign);
        futex_up(&malloc_futex);
        
        return block;
}

void *realloc(const void *addr, const size_t size)
{
        if (addr == NULL)
                return malloc(size);
        
        futex_down(&malloc_futex);
        
        /* Calculate the position of the header. */
        heap_block_head_t *head =
            (heap_block_head_t *) (addr - sizeof(heap_block_head_t));
        
        block_check(head);
        malloc_assert(!head->free);
        
        heap_area_t *area = head->area;
        
        area_check(area);
        malloc_assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area));
        malloc_assert((void *) head < area->end);
        
        void *ptr = NULL;
        bool reloc = false;
        size_t real_size = GROSS_SIZE(ALIGN_UP(size, BASE_ALIGN));
        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 trailing free block.
                         */
                        block_init((void *) head, real_size, false, area);
                        block_init((void *) head + real_size,
                            orig_size - real_size, true, area);
                        heap_shrink(area);
                }
                
                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.
                 */
                heap_block_head_t *next_head =
                    (heap_block_head_t *) (((void *) head) + head->size);
                
                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, area);
                        split_mark(head, real_size);
                        
                        ptr = ((void *) head) + sizeof(heap_block_head_t);
                        next_fit = NULL;
                } else
                        reloc = true;
        }
        
        futex_up(&malloc_futex);
        
        if (reloc) {
                ptr = malloc(size);
                if (ptr != NULL) {
                        memcpy(ptr, addr, NET_SIZE(orig_size));
                        free(addr);
                }
        }
        
        return ptr;
}

void free(const void *addr)
{
        futex_down(&malloc_futex);
        
        /* Calculate the position of the header. */
        heap_block_head_t *head
            = (heap_block_head_t *) (addr - sizeof(heap_block_head_t));
        
        block_check(head);
        malloc_assert(!head->free);
        
        heap_area_t *area = head->area;
        
        area_check(area);
        malloc_assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area));
        malloc_assert((void *) head < area->end);
        
        /* 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 < area->end) {
                block_check(next_head);
                if (next_head->free)
                        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 > (void *) AREA_FIRST_BLOCK_HEAD(area)) {
                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,
                            area);
        }
        
        heap_shrink(area);
        
        futex_up(&malloc_futex);
}

void *heap_check(void)
{
        futex_down(&malloc_futex);
        
        if (first_heap_area == NULL) {
                futex_up(&malloc_futex);
                return (void *) -1;
        }
        
        /* Walk all heap areas */
        for (heap_area_t *area = first_heap_area; area != NULL;
            area = area->next) {
                
                /* Check heap area consistency */
                if ((area->magic != HEAP_AREA_MAGIC) ||
                    ((void *) area != area->start) ||
                    (area->start >= area->end) ||
                    (((uintptr_t) area->start % PAGE_SIZE) != 0) ||
                    (((uintptr_t) area->end % PAGE_SIZE) != 0)) {
                        futex_up(&malloc_futex);
                        return (void *) area;
                }
                
                /* Walk all heap blocks */
                for (heap_block_head_t *head = (heap_block_head_t *)
                    AREA_FIRST_BLOCK_HEAD(area); (void *) head < area->end;
                    head = (heap_block_head_t *) (((void *) head) + head->size)) {
                        
                        /* Check heap block consistency */
                        if (head->magic != HEAP_BLOCK_HEAD_MAGIC) {
                                futex_up(&malloc_futex);
                                return (void *) head;
                        }
                        
                        heap_block_foot_t *foot = BLOCK_FOOT(head);
                        
                        if ((foot->magic != HEAP_BLOCK_FOOT_MAGIC) ||
                            (head->size != foot->size)) {
                                futex_up(&malloc_futex);
                                return (void *) foot;
                        }
                }
        }
        
        futex_up(&malloc_futex);
        
        return NULL;
}

---