malloc_freelist.c File Reference

#include <linkedlist/ll.h>
#include <malloc.h>
#include <memory.h>
#include <stdint.h>

Include dependency graph for malloc_freelist.c:

Go to the source code of this file.

Classes
struct	alloc_node_t

Macros
#define	align_up(num, align)   (((num) + ((align)-1)) & ~((align)-1))
#define	ALLOC_HEADER_SZ   offsetof(alloc_node_t, block)
#define	MIN_ALLOC_SZ   ALLOC_HEADER_SZ + 32

Functions
static void	defrag_free_list (void)
static	LIST_INIT (free_list)
	__attribute__ ((weak))
void *	malloc (size_t size)
void	free (void *ptr)
void	malloc_addblock (void *addr, size_t size)
	Assign blocks of memory for use by malloc(). More...

---

Class Documentation

alloc_node_t

struct alloc_node_t

Definition at line 26 of file malloc_freelist.c.

Collaboration diagram for alloc_node_t:

Class Members
char *	block
ll_t	node
size_t	size

Macro Definition Documentation

align_up

#define align_up	(		num,
			align
	)		(((num) + ((align)-1)) & ~((align)-1))

Simple macro for making sure memory addresses are aligned to the nearest power of two

Definition at line 18 of file malloc_freelist.c.

ALLOC_HEADER_SZ

#define ALLOC_HEADER_SZ   offsetof(alloc_node_t, block)

We vend a memory address to the user. This lets us translate back and forth between the vended pointer and the container we use for managing the data.

Definition at line 37 of file malloc_freelist.c.

MIN_ALLOC_SZ

#define MIN_ALLOC_SZ   ALLOC_HEADER_SZ + 32

Definition at line 40 of file malloc_freelist.c.

Function Documentation

__attribute__()

__attribute__

(

(weak)

)

Definition at line 81 of file malloc_freelist.c.

{
    // Unused here, override to specify your own init functin
    // Which includes malloc_addblock calls
}

defrag_free_list()

void defrag_free_list ( void  )

static

When we free, we can take our node and check to see if any memory blocks can be combined into larger blocks. This will help us fight against memory fragmentation in a simple way.

Definition at line 58 of file malloc_freelist.c.

{
    alloc_node_t* b;
    alloc_node_t* lb = NULL;
    alloc_node_t* t;

    list_for_each_entry_safe(b, t, &free_list, node)
    {
        if(lb)
        {
            if((((uintptr_t)&lb->block) + lb->size) == (uintptr_t)b)
            {
                lb->size += sizeof(*b) + b->size;
                list_del(&b->node);
                continue;
            }
        }
        lb = b;
    }
}

References alloc_node_t::block, and alloc_node_t::size.

Referenced by free().

free()

void free

(

void *

ptr

)

Definition at line 128 of file malloc_freelist.c.

{
    alloc_node_t* free_blk;
    alloc_node_t* blk;

    // Don't free a NULL pointer..
    if(ptr)
    {
        // we take the pointer and use container_of to get the corresponding alloc block
        blk = container_of(ptr, alloc_node_t, block);

        // Let's put it back in the proper spot
        list_for_each_entry(free_blk, &free_list, node)
        {
            if(free_blk > blk)
            {
                list_insert(&blk->node, free_blk->node.prev, &free_blk->node);
                goto blockadded;
            }
        }
        list_add_tail(&blk->node, &free_list);

    blockadded:
        // Let's see if we can combine any memory
        defrag_free_list();
    }
}

References defrag_free_list(), and alloc_node_t::node.

LIST_INIT()

static LIST_INIT ( free_list  )

static

malloc()

void* malloc

(

size_t

size

)

Definition at line 87 of file malloc_freelist.c.

{
    void* ptr = NULL;
    alloc_node_t* blk = NULL;

    if(size > 0)
    {
        // Align the pointer
        size = align_up(size, sizeof(void*));

        // try to find a big enough block to alloc
        list_for_each_entry(blk, &free_list, node)
        {
            if(blk->size >= size)
            {
                ptr = &blk->block;
                break;
            }
        }

        // we found something
        if(ptr)
        {
            // Can we split the block?
            if((blk->size - size) >= MIN_ALLOC_SZ)
            {
                alloc_node_t* new_blk;
                new_blk = (alloc_node_t*)((uintptr_t)(&blk->block) + size);
                new_blk->size = blk->size - size - ALLOC_HEADER_SZ;
                blk->size = size;
                list_insert(&new_blk->node, &blk->node, blk->node.next);
            }

            list_del(&blk->node);
        }

    } // else NULL

    return ptr;
}

References align_up, ALLOC_HEADER_SZ, alloc_node_t::block, MIN_ALLOC_SZ, alloc_node_t::node, and alloc_node_t::size.

malloc_addblock()

void malloc_addblock	(	void *	addr,
		size_t	size
	)

Assign blocks of memory for use by malloc().

Initializes the malloc() backend with a memory address and memory pool size. This memory is assumed to be owned by malloc() and is vended out when memory is requested. Multiple blocks can be added.

NOTE: This API must be called before malloc() can be used. If you call malloc() before allocating memory, malloc() will return NULL because there is no available memory to provide to the user.

Parameters

addr	Pointer to the memory block address that you are providing to malloc()
size	Size of the memory block that you are providing to malloc()

Definition at line 156 of file malloc_freelist.c.

{
    alloc_node_t* blk;

    // let's align the start address of our block to the next pointer aligned number
    blk = (void*)align_up((uintptr_t)addr, sizeof(void*));

    // calculate actual size - remove our alignment and our header space from the availability
    blk->size = (uintptr_t)addr + size - (uintptr_t)blk - ALLOC_HEADER_SZ;

    // and now our giant block of memory is added to the list!
    list_add(&blk->node, &free_list);
}

References align_up, ALLOC_HEADER_SZ, alloc_node_t::node, and alloc_node_t::size.