making your own malloc function in C

Question

I need your help in this. I have an average knowledge of C and here is the problem. I am about to use some benchmarks to test some computer architecture stuff (branch misses, cache misses) on a new processor. The thing about it is that benchmarks are in C but I must not include any library calls. For example, I cannot use malloc because I am getting the error

"undefined reference to malloc" 

even if I have included the library. So I have to write my own malloc. I do not want it to be super efficient - just do the basics. As I am thinking it I must have an address in memory and everytime a malloc happens, I return a pointer to that address and increment the counter by that size. Malloc happens twice in my program so I do not even need large memory.

Can you help me on that? I have designed a Verilog and do not have so much experience in C.

I have seen previous answers but all seem too complicated for me. Besides, I do not have access to K-R book.

Cheers!

EDIT: maybe this can help you more: I am not using gcc but the sde-gcc compiler. Does it make any difference? Maybe that's why I am getting an undefined reference to malloc?

EDIT2: I am testing a MIPS architecture:

I have included:

#include <stdlib.h>

and the errors are:

undefined reference to malloc
relocation truncated to fit: R_MIPS_26 against malloc

and the compiler command id:

test.o: test.c cap.h
sde-gcc -c -o test.s test.c -EB -march=mips64 -mabi=64 -G -O -ggdb -O2 -S
    sde-as -o test.o test.s EB -march=mips64 -mabi=64 -G -O -ggdb
    as_objects:=test.o init.o

EDIT 3: ok, I used implementation above and it runs without any problems. The problem is that when doing embedded programming, you just have to define everything you are using so I defined my own malloc. sde-gcc didn't recognize the malloc function.

Answer 1

This is a very simple approach, which may get you past your 2 mallocs:

static unsigned char our_memory[1024 * 1024]; //reserve 1 MB for malloc
static size_t next_index = 0;

void *malloc(size_t sz)
{
    void *mem;

    if(sizeof our_memory - next_index < sz)
        return NULL;

    mem = &our_memory[next_index];
    next_index += sz;
    return mem;
}

void free(void *mem)
{
   //we cheat, and don't free anything.
}

If required, you might need to align the memory piece you hand back, so e.g. you always give back memory addresses that's on an address that's a multiple of 4, 8, 16 or whatever you require.

Answer 2

Trying a thread safe nos answer given above, I am referring his code with some changes as below:

static unsigned char our_memory[1024 * 1024]; //reserve 1 MB for malloc
static size_t next_index = 0;

static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

void *malloc(size_t sz)
{
    void *mem;
    pthread_mutex_lock(&lock);
    if(sizeof our_memory - next_index < sz){
        pthread_mutex_unlock(&lock);
        return NULL;
    }

    mem = &our_memory[next_index];
    next_index += sz;
    pthread_mutex_unlock(&lock);
    return mem;
}

void free(void *mem)
{
   //we cheat, and don't free anything.
} 

Answer 3

You need to link against libc.a or the equivilent for your system. If you don't use the standard C lib you won't get any of the startup code that runs before the main function either. Your program will never run....

You could either allocate a block of static data and use that in the place of malloc, like:

// char* fred = malloc(10000);
// equals

static char [100000] fred;

or call the standard malloc for a large block of continuous memory on startup and write yr own malloc type function to divide that down. In the 2nd case you would start benchmarking after the calling the system's malloc as to not effect the benchmarks.

Answer 4

I am sharing the complete approach for Malloc and free it works on every scenario. This is complimented using array. We can also implement using link list for metadata.

There are three Scenarios We have to Cover

1. Continuous Memory allocation: Allocate memory in continuous manner
2. Allocated memory between two allocated memory: When Memory is free to allocate in between two allocated memory block. we have to use that memory chunk for allocation.
3. Allocated from Initial block When Initial block is free.

for detailed You can see in diagram. Diagram for allocating algo of memory

Source code for malloc

#define TRUE        1
#define FALSE       0

#define MAX_ALOCATION_ALLOWED       20
static unsigned char our_memory[1024 * 1024];

static int g_allocted_number = 0;
static int g_heap_base_address = 0;

typedef struct malloc_info
{
    int address;
    int size;
}malloc_info_t;

malloc_info_t   metadata_info[MAX_ALOCATION_ALLOWED] ={0};

void* my_malloc(int size)
{
    int j =0;
    int index = 0 ;
    int initial_gap =0;
    int gap =0;
    int flag = FALSE;
    int initial_flag = FALSE;
    void *address = NULL;
    int heap_index = 0;
    malloc_info_t temp_info = {0};

    if(g_allocted_number >= MAX_ALOCATION_ALLOWED)
    {
        return NULL;
    }

    for(index = 0; index < g_allocted_number; index++)
    {
        if(metadata_info[index+1].address != 0 )
        {
            initial_gap = metadata_info[0].address - g_heap_base_address; /*Checked Initial Block (Case 3)*/
            if(initial_gap >= size)
            {
                initial_flag = TRUE;
                break;
            }
            else
            {
                gap = metadata_info[index+1].address - (metadata_info[index].address + metadata_info[index].size);  /*Check Gap Between two allocated memory (Case 2)*/
                if(gap >= size)
                {
                    flag = TRUE;
                    break;
                }
            }
        }
    }

    if(flag == TRUE)    /*Get Index for allocating memory for case 2*/
    {
        heap_index = ((metadata_info[index].address + metadata_info[index].size) - g_heap_base_address);
    
        for(j = MAX_ALOCATION_ALLOWED -1; j > index+1; j--)
        {
            memcpy(&metadata_info[j], &metadata_info[j-1], sizeof(malloc_info_t));
        }
    }
    else if (initial_flag == TRUE) /*Get Index for allocating memory for case 3*/
    {
        heap_index = 0;
        for(j = MAX_ALOCATION_ALLOWED -1; j > index+1; j--)
        {
            memcpy(&metadata_info[j], &metadata_info[j-1], sizeof(malloc_info_t));
        }
    }
    else /*Get Index for allocating memory for case 1*/
    {
        if(g_allocted_number != 0)
        {
            heap_index = ((metadata_info[index -1].address + metadata_info[index-1].size) - g_heap_base_address);
        }
        else    /* 0 th Location of Metadata for First time allocation*/
            heap_index = 0;
    }

    address = &our_memory[heap_index];
    metadata_info[index].address = g_heap_base_address + heap_index;
    metadata_info[index].size = size;

    g_allocted_number += 1;
    return address;
}

Now Code for Free

void my_free(int address)
{
    int i =0;
    int copy_meta_data = FALSE;
    
    for(i = 0; i < g_allocted_number; i++)
    {
        if(address == metadata_info[i].address)
        {
            // memset(&our_memory[metadata_info[i].address], 0, metadata_info[i].size);
            g_allocted_number -= 1;
            copy_meta_data = TRUE;
            printf("g_allocted_number in free = %d %d\n", g_allocted_number, address);
            break;
        }
    }
    
    if(copy_meta_data == TRUE)
    {
        if(i == MAX_ALOCATION_ALLOWED -1)
        {
            metadata_info[i].address = 0;
            metadata_info[i].size = 0;
        }
        else
            memcpy(&metadata_info[i], &metadata_info[i+1], sizeof(malloc_info_t));
    }
}

For testing Now Test code is

int main()
{
    int *ptr =NULL;
    int *ptr1 =NULL;
    int *ptr2 =NULL;
    int *ptr3 =NULL;
    int *ptr4 =NULL;
    int *ptr5 =NULL;
    int *ptr6 =NULL;
    
    g_heap_base_address = &our_memory[0];

    ptr = my_malloc(20);
    ptr1 = my_malloc(20);
    ptr2 = my_malloc(20);
    
    my_free(ptr);
    ptr3 = my_malloc(10);
    ptr4 = my_malloc(20);
    ptr5 = my_malloc(20);
    ptr6 = my_malloc(10);
    
    printf("Addresses are: %d, %d, %d, %d, %d, %d, %d\n", ptr, ptr1, ptr2, ptr3, ptr4, ptr5, ptr6);

    return 0;
}