/*

* malloc.c

*

* Very simple linked-list based malloc()/free().

*/

#include <stdbool.h>

#include <stdlib.h>

#include <assert.h>

#include "malloc.h"

/* Both the arena list and the free memory list are double linked

list with head node. This the head node. Note that the arena list

is sorted in order of address. */

static struct free_arena_header __malloc_head = {

{

ARENA_TYPE_HEAD,

0,

&__malloc_head,

&__malloc_head,

},

&__malloc_head,

&__malloc_head

};

static bool malloc_lock_nop(void) {return true;}

static void malloc_unlock_nop(void) {}

static malloc_lock_t malloc_lock = &malloc_lock_nop;

static malloc_unlock_t malloc_unlock = &malloc_unlock_nop;

static inline void mark_block_dead(struct free_arena_header *ah)

{

#ifdef DEBUG_MALLOC

ah->a.type = ARENA_TYPE_DEAD;

#endif

}

static inline void remove_from_main_chain(struct free_arena_header *ah)

{

struct free_arena_header *ap, *an;

mark_block_dead(ah);

ap = ah->a.prev;

an = ah->a.next;

ap->a.next = an;

an->a.prev = ap;

}

static inline void remove_from_free_chain(struct free_arena_header *ah)

{

struct free_arena_header *ap, *an;

ap = ah->prev_free;

an = ah->next_free;

ap->next_free = an;

an->prev_free = ap;

}

static inline void remove_from_chains(struct free_arena_header *ah)

{

remove_from_free_chain(ah);

remove_from_main_chain(ah);

}

static void *__malloc_from_block(struct free_arena_header *fp, size_t size)

{

size_t fsize;

struct free_arena_header *nfp, *na, *fpn, *fpp;

fsize = fp->a.size;

/* We need the 2* to account for the larger requirements of a

free block */

if (fsize >= size + 2 * sizeof(struct arena_header)) {

/* Bigger block than required -- split block */

nfp = (struct free_arena_header *)((char *)fp + size);

na = fp->a.next;

nfp->a.type = ARENA_TYPE_FREE;

nfp->a.size = fsize - size;

fp->a.type = ARENA_TYPE_USED;

fp->a.size = size;

/* Insert into all-block chain */

nfp->a.prev = fp;

nfp->a.next = na;

na->a.prev = nfp;

fp->a.next = nfp;

/* Replace current block on free chain */

nfp->next_free = fpn = fp->next_free;

nfp->prev_free = fpp = fp->prev_free;

fpn->prev_free = nfp;

fpp->next_free = nfp;

} else {

fp->a.type = ARENA_TYPE_USED; /* Allocate the whole block */

remove_from_free_chain(fp);

}

return (void *)(&fp->a + 1);

}

static struct free_arena_header *__free_block(struct free_arena_header *ah)

{

struct free_arena_header *pah, *nah;

pah = ah->a.prev;

nah = ah->a.next;

if (pah->a.type == ARENA_TYPE_FREE &&

(char *)pah + pah->a.size == (char *)ah) {

/* Coalesce into the previous block */

pah->a.size += ah->a.size;

pah->a.next = nah;

nah->a.prev = pah;

mark_block_dead(ah);

ah = pah;

pah = ah->a.prev;

} else {

/* Need to add this block to the free chain */

ah->a.type = ARENA_TYPE_FREE;

ah->next_free = __malloc_head.next_free;

ah->prev_free = &__malloc_head;

__malloc_head.next_free = ah;

ah->next_free->prev_free = ah;

}

/* In either of the previous cases, we might be able to merge

with the subsequent block... */

if (nah->a.type == ARENA_TYPE_FREE &&

(char *)ah + ah->a.size == (char *)nah) {

ah->a.size += nah->a.size;

/* Remove the old block from the chains */

remove_from_chains(nah);

}

/* Return the block that contains the called block */

return ah;

}

void *malloc(size_t size)

{

struct free_arena_header *fp;

if (size == 0)

return NULL;

/* Add the obligatory arena header, and round up */

size = (size + 2 * sizeof(struct arena_header) - 1) & ARENA_SIZE_MASK;

if (!malloc_lock())

return NULL;

void *result = NULL;

for (fp = __malloc_head.next_free; fp->a.type != ARENA_TYPE_HEAD;

fp = fp->next_free) {

if (fp->a.size >= size) {

/* Found fit -- allocate out of this block */

result = __malloc_from_block(fp, size);

break;

}

}

malloc_unlock();

return result;

}

/* Call this to give malloc some memory to allocate from */

void add_malloc_block(void *buf, size_t size)

{

struct free_arena_header *fp = buf;

struct free_arena_header *pah;

if (size < sizeof(struct free_arena_header))

return; // Too small.

/* Insert the block into the management chains. We need to set

up the size and the main block list pointer, the rest of

the work is logically identical to free(). */

fp->a.type = ARENA_TYPE_FREE;

fp->a.size = size;

if (!malloc_lock())

return;

/* We need to insert this into the main block list in the proper

place -- this list is required to be sorted. Since we most likely

get memory assignments in ascending order, search backwards for

the proper place. */

for (pah = __malloc_head.a.prev; pah->a.type != ARENA_TYPE_HEAD;

pah = pah->a.prev) {

if (pah < fp)

break;

}

/* Now pah points to the node that should be the predecessor of

the new node */

fp->a.next = pah->a.next;

fp->a.prev = pah;

pah->a.next = fp;

fp->a.next->a.prev = fp;

/* Insert into the free chain and coalesce with adjacent blocks */

fp = __free_block(fp);

malloc_unlock();

}

void free(void *ptr)

{

struct free_arena_header *ah;

if (!ptr)

return;

ah = (struct free_arena_header *)

((struct arena_header *)ptr - 1);

#ifdef DEBUG_MALLOC

assert(ah->a.type == ARENA_TYPE_USED);

#endif

if (!malloc_lock())

return;

/* Merge into adjacent free blocks */

ah = __free_block(ah);

malloc_unlock();

}

void get_malloc_memory_status(size_t *free_bytes, size_t *largest_block)

{

struct free_arena_header *fp;

*free_bytes = 0;

*largest_block = 0;

if (!malloc_lock())

return;

for (fp = __malloc_head.next_free; fp->a.type != ARENA_TYPE_HEAD; fp = fp->next_free) {

*free_bytes += fp->a.size;

if (fp->a.size >= *largest_block) {

*largest_block = fp->a.size;

}

}

malloc_unlock();

}

void set_malloc_locking(malloc_lock_t lock, malloc_unlock_t unlock)

{

if (lock)

malloc_lock = lock;

else

malloc_lock = &malloc_lock_nop;

if (unlock)

malloc_unlock = unlock;

else

malloc_unlock = &malloc_unlock_nop;

}