malloc.c

Go to the documentation of this file.

#include <sys/types.h>
#include <stdio.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h> /* memset */
#include <unistd.h>
#include <errno.h>
#include <malloc.h>

#include <list.h>

#include <debug.h>
#include <interrupt.h>

#define CAN_BE_MERGED(prev, next) \
        ((struct chunk*)(((struct chunk*)(prev))->ptr + ((struct chunk*)(prev))->size) == next)

#define ALIGNED(align, size) \
        ((uint32_t)((uint32_t)(size) + ((align) - ((uint32_t)(size) & ((align) - 1)))))

struct chunk {
        struct list_head head; 
        ssize_t size; 
        char ptr[]; 
} __PACKED;

static LIST_HEAD(__used);

static LIST_HEAD(__free);

static struct chunk_stat {
        unsigned long base;
        struct {
                unsigned long total;
                unsigned long used;
        } size;
} s_stat;

static inline struct chunk *find_item(void *ptr, uint32_t align)
{
        struct list_head *pos;
        struct chunk *item;

        list_for_each(pos, &__used) {
                item = list_entry(pos, struct chunk, head);
                if ((uint32_t)item < (uint32_t)ptr && (ALIGNED(align, item->ptr) == (uint32_t)ptr)) {
                        return item;
                }
        }

        return NULL;
}

void malloc_init(uint32_t base, uint32_t size)
{
        struct chunk *item;

        item = (struct chunk*)base;
        item->size = size - sizeof(*item);

        s_stat.base = (unsigned long)base;
        s_stat.size.total = item->size;
        s_stat.size.used = 0;

        list_add_tail(&item->head, &__free);
}

void *malloc(size_t size)
{
        struct chunk *item;
        struct list_head *pos;
        struct list_head *n;
        int chunk_size;
        register int internal_fragment;
        uint32_t align;
        unsigned long flags;

        irq_local_save(&flags);
        NEED_LOCK_TEST_BEGIN

        align = sysconf(_SC_PAGESIZE);
        chunk_size = size + sizeof(*item);

        do {
                list_for_each_safe(pos, n, &__free) {
                        item = list_entry(pos, struct chunk, head);

                        internal_fragment = item->size - chunk_size;
                        if (internal_fragment < 0) {
                                continue;
                        }

                        if (internal_fragment <= sizeof(*item)) {
                                list_del(pos);
                        } else {
                                struct chunk *new_item;
                                item->size -= chunk_size;
                                new_item = (struct chunk *)(item->ptr + item->size);
                                new_item->size = size;
                                item = new_item;

                                s_stat.size.used += chunk_size;
                        }

                        list_add_tail(&item->head, &__used);
                        NEED_LOCK_TEST_END
                        irq_local_restore(flags);
                        return item->ptr;
                }
        } while (sbrk(ALIGNED(align, chunk_size)));

        NEED_LOCK_TEST_END
        irq_local_restore(flags);
        return NULL;
}

void *calloc(size_t nmemb, size_t size)
{
        void *ret;

        size *= nmemb;
        if (!size) {
                return NULL;
        }

        ret = malloc(size);
        if (!ret) {
                return NULL;
        }

        memset(ret, 0, size);
        return ret;
}

int posix_memalign(void **memptr, size_t align, size_t size)
{
        struct chunk *item;
        struct list_head *pos;
        struct list_head *n;
        uint32_t chunk_size;
        register int internal_fragment;
        unsigned long flags;

        irq_local_save(&flags);
        NEED_LOCK_TEST_BEGIN

        do {
                list_for_each_safe(pos, n, &__free) {
                        item = list_entry(pos, struct chunk, head);

                        chunk_size = ALIGNED(align, item->ptr);
                        chunk_size -= (uint32_t)item->ptr;
                        chunk_size += size + sizeof(*item);

                        internal_fragment = item->size - chunk_size;
                        if (internal_fragment < 0) {
                                continue;
                        }

                        if (internal_fragment <= sizeof(*item)) {
                                list_del(pos);
                        } else {
                                struct chunk *new_item;

                                item->size -= chunk_size;
                                new_item = (struct chunk *)(item->ptr + item->size);
                                new_item->size = size;
                                item = new_item;

                                s_stat.size.used += chunk_size;
                        }

                        list_add_tail(&item->head, &__used);

                        *memptr = (void *)ALIGNED(align, item->ptr);
                        NEED_LOCK_TEST_END
                        irq_local_restore(flags);
                        return 0;
                }
        } while (sbrk(ALIGNED(align, chunk_size)));

        NEED_LOCK_TEST_END
        irq_local_restore(flags);
        return -ENOMEM;
}

void free(void *ptr)
{
        struct list_head *pos;
        struct list_head *n;
        struct chunk *item;
        struct chunk *tmp;
        int merged;
        uint32_t align;
        unsigned long flags;

        irq_local_save(&flags);
        NEED_LOCK_TEST_BEGIN

        item = NULL;

        align = sysconf(_SC_PAGESIZE);
        if (ALIGNED(align, ptr) == (uint32_t)ptr) {
                item = find_item(ptr, align);
        }

        if (!item) {
                item = container_of(ptr, struct chunk, ptr);
        }

        list_del(&item->head);

        s_stat.size.used -= (item->size + sizeof(*item));

        merged = 0;
        list_for_each_safe(pos, n, &__free) {
                tmp = list_entry(pos, struct chunk, head);

                if (tmp > item) {
                        if (CAN_BE_MERGED(item, tmp)) {
                                item->size += tmp->size + sizeof(*tmp);
                                tmp->head.next->prev = &item->head;
                                if (!merged) {
                                        tmp->head.prev->next = &item->head;
                                        item->head = tmp->head;
                                        merged = 1;
                                }
                                continue;
                        }

                        if (!merged) {
                                tmp->head.prev->next = &item->head;
                                item->head.prev = tmp->head.prev;

                                item->head.next = &tmp->head;
                                tmp->head.prev = &item->head;
                        }

                        break;
                }

                if (CAN_BE_MERGED(tmp, item)) {
                        tmp->size += item->size + sizeof(*item);
                        item = tmp;
                        merged = 1;
                        continue;
                }
        }

        NEED_LOCK_TEST_END
        irq_local_restore(flags);
}

int brk(void *ptr)
{
        unsigned long total;
        unsigned long boundary;
        struct chunk *item;
        unsigned long flags;

        irq_local_save(&flags);
        NEED_LOCK_TEST_BEGIN

        total = (unsigned long)ptr - s_stat.base;
        if (s_stat.size.used > total) {
                NEED_LOCK_TEST_END
                irq_local_restore(flags);
                return -EBUSY;
        }

        boundary = s_stat.base + s_stat.size.total;
        item = list_entry(__free.prev, struct chunk, head);

        if (((unsigned long)item + item->size) == boundary) {
                ssize_t tmp;
                tmp = item->size + total - s_stat.size.total;
                if (tmp < 0) {
                        NEED_LOCK_TEST_END
                        irq_local_restore(flags);
                        return -EBUSY;
                }

                item->size = tmp;
                s_stat.size.total = total;
        } else {
                /* 새로운 여유 청크를 만들고,
                 * 여유 청크 목록에 추가한다.
                 */
                if ((unsigned long)ptr <= boundary) {
                        NEED_LOCK_TEST_END
                        irq_local_restore(flags);
                        return -EBUSY;
                }

                item = (struct chunk*)boundary;
                item->size = (ssize_t)((unsigned long)ptr - boundary);
                item->size -= sizeof(*item);

                list_add_tail(&item->head, &__free);
        }

        NEED_LOCK_TEST_END
        irq_local_restore(flags);
        return 0;
}

void *sbrk(intptr_t increment)
{
        unsigned long boundary;
        struct chunk *item;
        unsigned long flags;

        irq_local_save(&flags);
        NEED_LOCK_TEST_BEGIN

        boundary = s_stat.base + s_stat.size.total;
        item = list_entry(__free.prev, struct chunk, head);

        if (((unsigned long)item + item->size) == boundary) {
                if ((item->size + increment) < 0) {
                        NEED_LOCK_TEST_END
                        irq_local_restore(flags);
                        return NULL;
                }

                item->size += increment;
        } else {
                if (increment <0) {
                        NEED_LOCK_TEST_END
                        irq_local_restore(flags);
                        return NULL;
                }

                item = (struct chunk*)boundary;
                item->size = increment - sizeof(*item);
                list_add_tail(&item->head, &__free);
        }
        boundary += increment;

        NEED_LOCK_TEST_END
        irq_local_restore(flags);
        return (void*)boundary;
}

void *valloc(size_t size)
{
        return memalign(sysconf(_SC_PAGESIZE), size);
}

void *memalign(size_t boundary, size_t size)
{
        void *ptr;

        if (posix_memalign(&ptr, boundary, size) < 0) {
                return NULL;
        }

        return ptr;
}

/*
int chunk_stat_total(void)
{
        return s_stat.size.total;
}

int chunk_stat_used(void)
{
        return s_stat.size.used;
}

unsigned long chunk_stat_base(void)
{
        return s_stat.base;
}
*/

/* End of a file */