I'm trying to implement my own version of malloc() function in c. I decided to keep track of my allocated blocks using a linked list of meta-data objects that would store some information about the allocated chunk and and place it right before the chunk. Now long story short while debugging I came across the fact that my linked list is behaving very strangely. here's a piece of the code to help understanding the problem.

typedef struct meta_data
{
   size_t size;
   int free;
   struct meta_data* next;
}meta_data;


meta_data* global_base;

void *mymalloc(size_t size)
{
  if(size > 0)
  {
    meta_data block_meta;
    void* pointer = sbrk(size   block_size);

    block_meta.size = size;
    block_meta.next = NULL;
    block_meta.free = 0;


    if(!global_base) //first allocation
    {
        global_base = &block_meta;
    }
    else
    {
        block_meta.next = global_base;
    }
    return pointer;
  }
  else
  {
    return NULL;
  }
}

I wrote this code which I assume will append a new item to the tail of my global_base (linked list) every time I call mymalloc(<some_size>); however when I tried to debug and make sure that my linked list is in order by calling mymalloc() couple of times and check is my linked list is being populated properly

void printList()
{
    meta_data * node = global_base;
    while (node->next != NULL)
    {
        printf("%zu", node->size);
        printf(" -> ");
        node = node->next;
    }
    printf(" \n ");
 }

int main()
{

   mymalloc(10);
   mymalloc(8);
   mymalloc(4);
   printList();
   
   return 0;
}

I expected my output to be 10 -> 8 -> 4 however it was 4 -> 4 -> 4 -> 4 -> 4 ..... and goes into an infinite loop

any idea where am I going wrong with this code. I'm a little new to programming with C so my only guess is that I'm making use of reference & and pointer * improperly. furthermore I have seen tones of code where the assignment of struct's attribute is happening with the use of -> but I could only use . to make it (could this be the problem anyhow)?

help is appreciated thanks guys

CodePudding user response：

There are multiple problems with your approach:

• the meta_data block_meta; is a local variable. You cannot use that to link the blocks. Local variables are reclaimed when the function exits. You should use global memory retrieved from the system with sbrk, pointed to by pointer.

• the print loop is incorrect: you should write while (node != NULL) to print all blocks.

CodePudding user response：

Your code has dozens of issues which I will address.

1. Now the problem with your code, in fact the biggest issue with it is that the myalloc function doesn't create a new block_meta node. It just declares a block_meta variable (which will end up on the stack and even worse is a recipe for disastrous bugs I believe the infinite loop is a result of this). You should you use the sbrk function to create a meta_data node before doing anything like so:

...
meta_data *block_meta = sbrk(sizeof(meta_data));

block_meta->size = size;
block_meta->next = NULL;
block_meta->free = 0;

if(!global_base)
{
   global_base = block_meta;
}

2. The myalloc function checks to see if global_base has been assigned, that is if there is a root node in the linked list. If there is one it should simply tell the current variable to link itself to the global_base that is point it's next variable at global_base, this is a big error. Firstly, the global_base is the root node and it makes no sense to tell the current node to link itself to the root of the linked list, it's supposed to link itself to the next node not the root. Secondly, the reference to the previous node is lost which means it's not a linked list anymore. A proper solution would be saving the current node in a variable using a static variable which prevents it from getting lost when the myalloc function exits:

...
static meta_data *curr;

then right before returning the pointer to the newly allocated block you add this line to hold the node that had been newly created:

...
curr = block_meta;
return pointer;

now return to the erring else statement and change that to to ensure that the previous node points to the current node:

...
else
{
   curr->next = block_meta;
}