malloc and free implementation

[ms95]

i want to implement a kind of malloc and free function for a course project , now i have done something but i dont know whats the problem with access violation in this line :

head->next = (struct block_meta *) allocate(sizeof(struct block_meta));

i'd be glad if someone can help me fix it or even if someone have any better idea for implementing this , ( cause obviously my implementation has a lot of problems) . thanks

    #include<stdio.h>
    #include <stdlib.h>
    #define DATA_SEG_SIZE 65536
    void* allocate(int size);

    char data_seg[DATA_SEG_SIZE];
    char* heap_top = data_seg;
    char* stack_top = data_seg + DATA_SEG_SIZE - 1;

    struct block_meta
    {
        unsigned char size;
        struct block_meta *next;
        void* block_ptr;
    };
    struct block_meta * first, *head;

    void* search_for_free(int size)
    {
        head = first;
        while ( head != NULL )
        {
            if ( head->size == size )
                return head->block_ptr;
            else
                head = head->next;
        }
        return NULL;
    }
    void free_allocated(void* ptr, int size)
    {
        head = first;
        if(head == NULL){
            first = (struct block_meta *) allocate(sizeof(struct block_meta));
            head = first;
        }
        else if(head->next == NULL){
            head->next = (struct block_meta *) allocate(sizeof(struct block_meta));
            head = head->next;
        }
        head->size = size;
        head->block_ptr = ptr;
        head->next = NULL;
    }
    void* allocate(int size) 
{
    if ( search_for_free(size) != NULL )
        return search_for_free(size);
    else if ( heap_top >= stack_top )
        return NULL;
    heap_top += size;
    return (heap_top - size);
}




   int main()
{
    int *num;
    int *p;
    free_allocated(num, 8 * sizeof(char));
    p = (int *) allocate(8 * sizeof(char));
    free_allocated(p, 8 * sizeof(char));
    p = (int*) allocate(50*sizeof(char));
    return 0;
}

[deceptikon]

What does allocate look like?

[ms95]

im sorry i've forgotten to add the testcases and alocate function . i've added them above .
thanks

[biplobsaheb]

you ra very fine

[biplobsaheb]

how to my pc spied???????????

[Moschops]

Your function search_for_free sets head to NULL. So on the line in question, you call allocate, which then calls search_for_free, which sets head to NULL, and then you try to access head->next, and insta-segFault.

[Schol-R-LEA]

A few pieces of advice:

• The heart of the problem you are having is that you haven't initialized the free memory handle (first) before using it. I would start by writing a function to do that and calling it at the start of the program (the reason you don't need to do this explicitly in C applications is because it is done for you as part of the setup for the program before main() is run).
• If you are using a modern compiler (one that defaults to C99 or later), rather than using char as the memory type, use uint8_t. This is more precise and specific about the size of the elements. You'll need to #include <stdint.h> to get the size-specific integer types, but that's a minor consideration. I mention this now mainly because it is relevant to the next issue.
• You are using an 8-bit unsigned char for the block sizes. This means that the blocks are a maximum of 255 bytes long. Since you actually have a memory space of 65536, you would need a 16-bit block size to span the whole memory space, or else force the memory to be segmented into 256 pages. I recommend using a uint16_t instead, or if that isn't an option, an unsigned short (though the exact size of that isn't guaranteed to be 16 bits IIRC).
• In search_for_free(), you have the comparison look for an exact match to the size of the block size being allocated. Exact Fit algorithms rarely work unless the sizes are restricted to a small specified range somehow (e.g., they can only be allocated in blocks of 1, 2, 4, or 8). Even a Best Fit algorithm works better, but that has problems of its own.
• The problem with a Best Fit algorithm is fragmentation: you end up with a lot of small pieces that cannot be allocated because nothing will fit in them. Rather than searching for an Exact Fit or Best Fit, you may be better using a Worst Fit algorithm, where you find the largest block available and cutting into two pieces. This reduces the problem of fragmentation, because the remaining part is usually more than large enough to allocate a section out of.
• The other advantage of Worst Fit is that you can avoid most of your searching, provided you keep the free memory list sorted largest to smallest. When you allocate a new block, you remove the first block from the list, partition it, then do a search for where to insert the remaining fragment back into the list.
• Don't forget to consider block merging when freeing memory. When you go to insert a block back into the free list, first check to see if any other blocks are adjacent to it, and if they are, remove the adjacent block(s) from the list, merge the blocks into a single larger block, then insert it into the free list.

[ms95]

thanks for your answeres .
about the last answere i'd completely consider them in my final implementation . but its just kind of prototype for now .

but about the problem of the question , i've tried to do what the user Moschops said but unfortuanately i coudn't anywhere .
can you please tell me what to do exactly ?

thanks

[Moschops]

You need to think about your search_for_free function, and how your allocate function handles what comes back from search_for_free. There is a while loop that goes around and around until one of two things happens:

1) head->size == size

Presumably this means that you found some memory of the right size.

2) head becomes NULL (the while loop condition)

Presumably in your scheme, this means that you have searched through all the memory looking for something the right size, and you didn't find anything. Your memory allocation has failed, but you aren't handling it well and you end up trying to use head, even though you set it to NULL. This isn't a syntax problem; your algorithm just plain doesn't handle this properly and you need to think about how to handle this case properly.

[ms95]

thanks i got the point .
if you have noticed , when i use my allocate function and will assign its value to first and then set the head to first the problem will occure because it does not assign anything to first and the first will permenently be NULL but when i use the default malloc the the adress of first will be changed from NULL to its new adress ,
so i guess the problem is in my allocate function . but as far as i see it it just do quit right . it returns a void pointre as the real malloc does . can anyone see any problem with the allocate function ?

thanks

[Schol-R-LEA]

While I do indeed see some serious issues with how allocate() is implemented, I would say the real problem is happening even earlier. As I said before, what is really going on is that you haven't initialized first to any value at all, whic means that there is no value to check. You need a function that expressly initializes first and runs before either any of your other functions are called:

struct block_meta* init_memory_area(uint8_t mem[], uint16_t size)
{
    struct block_meta* first = malloc(sizeof(struct block_meta));
    first->size = size;
    first->next = NULL;
    first->block_ptr = mem;

    return first;
}

Actually, before we do that, let's rearrange things a little bit:

alloc.h

#ifndef ALLOC_H
#define ALLOC_H 1

#include <stdbool.h>
#include <stdint.h>

struct block_meta
{
    uint8_t size;
    struct block_meta *next;
    void* block_ptr;
};

void* allocate(int size);
bool free_allocated(void* ptr);

#endif

alloc.c

#include <stdlib.h>
#include <stdint.h>
#include "alloc.h"

const unit16_t DATA_SEG_SIZE = UINT16_MAX;
char data_seg[DATA_SEG_SIZE];

struct block_meta* first;

struct block_meta* init_memory_area(uint8_t mem[], uint16_t size);
void* search_for_free(int size);

struct block_meta* init_memory_area(uint8_t mem[], uint16_t size)
{
    struct block_meta* first = malloc(sizeof(struct block_meta));
    first->size = size;
    first->next = NULL;
    first->block_ptr = mem;

    return first;
}

void* search_for_free(int size)
{
    struct block_meta* head;

    if (first == NULL)
    {
        init_memory_area(

    head = first;

    while ( head != NULL )
    {
        if ( head->size == size )
            return head->block_ptr;
        else
            head = head->next;
    }
    return NULL;
}

void free_allocated(void* ptr, int size)
{
    struct block_meta* head = first;

    if(head == NULL)
    {
        first = (struct block_meta *) allocate(sizeof(struct block_meta));
        head = first;
    }
    else if(head->next == NULL)
    {
        head->next = (struct block_meta *) allocate(sizeof(struct block_meta));
        head = head->next;
    }
    head->size = size;
    head->block_ptr = ptr;
    head->next = NULL;
}

void* allocate(int size) 
{
    if (

    if (search_for_free(size) != NULL)
        return search_for_free(size);
    else if ( heap_top >= stack_top )
        return NULL;
    heap_top += size;
    return (heap_top - size);
}

[Schol-R-LEA]

Let me make some corrections to that:

[rubberman]

So, where are you getting free-store from the operating system? Usually one uses sbrk() for that. That provides you with heap store that you can allocate with calloc/malloc et al. And you use that store to provide memory to applications when requested. It doesn't come magically... you have to first get it from the operating system.

[ms95]

the problem is that im trying to write this on a home made mini os , which means that i dont have any library but the pure c .

[Schol-R-LEA]

Is this 'home-made mini OS' running as an application on an existing system, or are you actually booting it from the bare hardware (or the virtualized equivalent thereof)? I am assuming the latte, which means it is more of an OS simulation than a full OS, not that that is a bad thing; writing an actual operating system is an enormous task, and chances are you aren't up to it yet.

Depending on how serious you are about this, you might want to look at the OSDev wiki, especially the sections on memory management.

Mind you, the memory management you are currently working on is at the application level, not the OS level. Those are two quite different things. Generally speaking, the OS level memory management has to deal with the memory for the entire system, not just some arbitrary size section, and had to deal with issues of the mapping of virtual memory to physical memory, setting up separate process memory spaces, and handling paging, among other things. Application level memory management is a significantly simpler matter, but still not easy.

[Moschops]

As I interpret the code, the big bank of memory to be used for all this is
char data_seg[DATA_SEG_SIZE];
being 65536 bytes of memory for playing with. This is the memory that the OP is meant to be using to allocate from.

[Nutster]

The first thing you do in main is pass the uninitialized pointer num to free_allocated(). This is probably a mistake, especially considering what free_allocated() does. I realize this is a much smaller issue than the other things mentioned, but it can cause things to blow up just as well.

[ms95]

actualy im running the os on the hardware from boot up in protect mode and just for experience .
which i suppose to write some functions to make it easier to use maybe someday for others .

if you are (Schol-R-LEA) interested to know what im doing i can send you the files as soon as i've done with them . and maybe i could get some advices :D just let me know .

and thanks for the answeres of other firends :)

[ms95]

guys one other question got stuck in my mind .
why this in this line nothing will be assigned to head.next despite that my allocate function is returning a pointer .

head->next = (struct block_meta *) allocate(sizeof(struct block_meta));

and why does it work very good with the real malloc ?

head->next = (struct block_meta *) malloc(sizeof(struct block_meta));

is it anything wrong with my allocate function , which should i fix ?

[Moschops]

why this in this line nothing will be assigned to head.next despite that my allocate function is returning a pointer .

Your alllocate function can return a pointer, or NULL. If it returns NULL, you're setting head->next to NULL.

[ms95]

here is the issue . it doesn't return NULL , it returns a memory adress just like malloc does there , but the different is when i use my allocate function the address can not be assigned to head->next but when i use malloc it does .
whats the problem ?

[Moschops]

Both malloc and your function return a void pointer. It is effectively impossible that you can assign the void pointer that comes back from malloc, but not the one that comes back from your function. They're just void pointers, and assigning doesn't even try to dereference that pointer, so it doesn't matter what value it has.

So when you say "can not be assigned", I just don't believe you. What happens when you try to assign it? Does the code refuse to compile? Does it crash when you try to make that assignment?

[ms95]

it just crash with access violation error .
if you dont believe me just give it a try, debug it . when you replace the allocate with malloc in the line i've mentioned before, the whole code will work without a hitch . because of that im suspected on allocate function .