CODEWITHSUNDEEP
c
Fox
Fox

Reputation: 9

My malloc doesn't update the heap properly

I'm trying to implement my own malloc and then test it by dumping the heap to see what I've managed to accomplish. It compiles fine but when I run it, I get the output of 

head->[1:0:8]->NULL
this is a test program

after which it promptly crashes. It looks like the way I implemented my malloc, it is able to allocate the space for *this and *is, but that's all. Anyone have any ideas why this might be?

My main.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>


#define MALLOC(n) my_malloc(n)
#define DUMP_HEAP() dump_heap()
void* my_malloc(int);

int main()
{
  char *this = MALLOC(5);
  char *is = MALLOC(3);
  char *a = MALLOC(2);
  char *test = MALLOC(5);
  DUMP_HEAP();

  strcpy(this, "this");
  strcpy(is, "is");
  strcpy(a, "a");
  strcpy(test, "test");
  strcpy(program, "program");
  printf("%s %s %s %s %s\n", this, is, a, test, program);
  DUMP_HEAP();

  return 0;
}

My malloc.c

#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <assert.h>

struct Block 
{
    int occ;             
    int size;            
    struct Block *prev;   
    struct Block *next;  
};

static struct Block *head = NULL; 

void *my_malloc(int size)
{
    void *pointer;
    pointer = (void*)sbrk(size);
    if(head == NULL)
    {
            head = pointer;
            head->occ = 1;
            head->prev=NULL;
            head->next=NULL;
            head->size = size;

            return (void*)head+sizeof(struct Block);
    }
    else
    {
            struct Block* new ;
            new = pointer;
            head->next = new;
            new->size = size;
            new->occ = 1;
            new->prev = head;
            new->next = NULL;
            head = new;

            return (void*)new+sizeof(struct Block);
    }
}

void dump_heap()
{
  struct Block *cur;
  printf("head->");
  for(cur = head; cur != NULL; cur = cur->next) 
  {
    printf("[%d:%d:%d]->", cur->occ, (char*)cur - (char*)head, cur->size);
    assert((char*)cur >= (char*)head && (char*)cur + cur->size < (char*)sbrk(0));
    if(cur->next != NULL) assert(cur->next->prev == cur); 
  }
  printf("NULL\n");
}

Upvotes: 0

Views: 172

Answers (1)

Matt
Matt

Reputation: 161

You aren't accounting for the size of the Block struct when asking the system for memory.

Compare this line:

pointer = (void*)sbrk(size);

to how you're attempting to account for the struct later:

return (void*)head+sizeof(struct Block);

You should be accounting for the size of the Block in the sbrk call:

pointer = (void*)sbrk(size + sizeof(struct Block));

Also, as has been pointed out, you should not do pointer arithmetic on void*. So your return statements should leave the head pointer uncasted and just add 1 to account for the block size:

return (void*)(head + 1);

Also also, upon further discussion it is clear that head is being used as the tail of the linked list. This introduces a bug in dump_heap. You may want to rename head to tail and maintain a proper head, one which only ever changes in malloc when it was previously NULL.

Upvotes: 2

Related Questions