Own Malloc implementation freeze at brk

Question

for practice I'm currently trying to write my own malloc function in c. So my question is, after some allocation from the heap my program will freeze. I found the code segment which will couse the freeze and it'll freeze when i call the brk sys call. I allready tried to unlock my mutex there but this didn't work. To test it i wrote a permanent loop and allocate memory in an array and freed it randomly.

static list *head = NULL;
static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

typedef struct list
{         
  size_t size_;                
  int free_;                  
  struct list *next_;      
  struct list *previouse_;
} block;

void blockAdd(block *href, size_t size)
{
  href->free_ = FALSE;
  href->next_ = NULL;
  href->previouse_ = NULL;

  if (!head || head > href)
  {
    if (head)
    {
      head->previouse_ = href;
    }
    href->size_ = size + sizeof(block);
    href->next_ = head;
    head = href;
  }
  else
  {
    href->next_ = NULL;
    block *current = head;

    while (current->next_ && current->next_ < href)
    {
      current = current->next_;
    }
    href->size_ = size + sizeof(block);
    href->next_ = current->next_;
    href->previouse_ = current;
    current->next_ = href;
  }
}

void *findExactSizeMatch(size_t size)
{
  block *href = head;
  size_t t = size + sizeof(block);

  while (href)
  {
    if (href->size_ == (size + sizeof(block)) && href->free_)
    {
      href->free_ = FALSE;
      return href;
    }
    href = href->next_;
  }
  return NULL;
}

void *findLagerBlock(size_t size)
{
  block *href = head;

  while (href)
  {
    if (href->free_ && href->size_ > size)
    {
      return split(href, size);
    }
    href = href->next_;
  }

  return NULL;
}

void *allocateMemory(size_t size)
{
  block *new_block = sbrk(BLOCK_SIZE(size));

  if (new_block == SBRK_FAILED)
  {
    exit(1);
  }
  blockAdd(new_block, size);

  return new_block;
}

bool checkAllFree()
{
  block *href = head;

  while (href)
  {
    if (!href->free_)
    {
      return FALSE;
    }
    href = href->next_;
  }
  return TRUE;
}

void freeList(block *ptr)
{
  if (checkAllFree())
  {
    if (brk(ptr) == BRK_FAILED)
    {
     exit(1);
    }
    head = NULL;
  }
}

void merge()
{
  block *href = head;

  while (href && href->next_)
  {
    if (href->free_ && href->next_->free_)
    {
      href->size_ = href->next_->size_;
      href->next_ = href->next_->next_;
    }
    href = href->next_;
  }
}

//--------------------------Here it makes some strange things
shrinkHeap()
{
  block *href = head;

  while (href && href->next_)
  {
    href = href->next_;
  }

  if (href && href->free_)
  {
    if (brk(href) == BRK_FAILED)
    {
      exit(1);
    }
    href->previouse_->next_ = href->next_;
  }
}

void *malloc(size_t size)
{
  if (!size)
  {
    return NULL;
  }
  pthread_mutex_lock(&mutex);

  block *new_list = NULL;

  new_list = findExactSizeMatch(size);
  if (new_list)
  {
    pthread_mutex_unlock(&mutex);
    return new_list + sizeof(block);
  }

  new_list = allocateMemory(size);
  pthread_mutex_unlock(&mutex);

  return new_list + sizeof(block);
}

void free(void *ptr)
{
  if (!ptr || !head)
  {
    return;
  }
  pthread_mutex_lock(&mutex);

  block *pref = ptr - sizeof(block);

  pref->free_ = TRUE;

  freeList(pref);
  shrinkHeap();
  merge();

  pthread_mutex_unlock(&mutex);
}

I don't know why, but brk freeze my program.

Thx for your help!

Answer 1

There are multiple problems in your code:

• in blockAdd, you fail to update href->next_->previouse_ if href->next_ is not NULL in the else branch.

• findLagerSize should be changed to findLargerSize and should use size + sizeof(block) to locate an appropriate block of memory.

• allocateMemory is incorrect too: the size passed to sbrk should include sizeof(block) extra bytes, the block thus allocated should be inserted into the heap and split if it is larger than size + sizeof(block).

• in freeList, in case checkAllFree() returns true, you should call brk(head), not brk(ptr).

• in merge, you do not update href->size correctly: you should combine the sizes. Furthermore you do not upate href-_next->previouse_.

• The prototype for shrinkHeap should have a return type and an argument list:

  void shrinkHeap(void)
  

• In shrinkHeap you must update the link before calling brk as the pointer may become invalid after the call. Furthermore, you must test if href->previouse_ is not NULL and this update can be simplified as:

      if (href->previouse_ != NULL)
          href->previouse_->next_ = NULL;
  

• Your malloc function has a flaw: return new_list + sizeof(block); does not return the pointer to the allocated block, but one much farther away, causing the application to write beyond the end of the allocated block, potentially corrupting the arena. Furthermore, the pointer computed by free does not point to the block, causing further corruption of the arena even if the program did not write to the memory block and invoking undefined behavior.

  In both places in malloc(), you should write this instead:

      return new_list + 1;
  

• Similarly in free(), but not necessarily causing an error, you should avoid performing arithmetics on void pointers, cast them as unsigned char * for portable code:

  block *pref = (void *)((unsigned char*)ptr - sizeof(block));
  

  Or perform the arithmetics after proper typing:

  block *pref = ptr;
  ptr -= 1;
  

Here is a modified version:

static struct list *head = NULL;
static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

typedef struct list {
    size_t size_;           // block size, including header
    int free_;              // free indicator, true or false
    struct list *next_;
    struct list *previouse_;
} block;

void blockAdd(block *href, size_t size) {
    href->free_ = FALSE;
    href->size_ = size + sizeof(block);
    href->next_ = NULL;
    href->previouse_ = NULL;

    if (!head || head > href) {
        if (head) {
            head->previouse_ = href;
        }
        href->next_ = head;
        head = href;
    } else {
        block *current = head;
        while (current->next_ && current->next_ < href) {
            current = current->next_;
        }
        href->next_ = current->next_;
        if (href->next_) {
            href->next_->previouse_ = href;
        }
        href->previouse_ = current;
        current->next_ = href;
    }
}

void *findExactSizeMatch(size_t size) {
    block *href = head;
    size_t t = size + sizeof(block);

    while (href) {
        if (href->free_ && href->size_ == t) {
            href->free_ = FALSE;
            return href;
        }
        href = href->next_;
    }
    return NULL;
}

void *findLargerBlock(size_t size) {
    block *href = head;
    size_t t = size + sizeof(block);

    while (href) {
        if (href->free_ && href->size_ > t) {
            return split(href, size);
        }
        href = href->next_;
    }
    return NULL;
}

void *allocateMemory(size_t size) {
    /* should add size of `block` */
    block *new_block = sbrk(BLOCK_SIZE(size));

    if (new_block == SBRK_FAILED) {
        exit(1);
    }
    /* should split new_block if BLOCK_SIZE(size) > size */
    blockAdd(new_block, size);

    return new_block;
}

bool checkAllFree() {
    block *href = head;

    while (href) {
        if (!href->free_) {
            return FALSE;
        }
        href = href->next_;
    }
    return TRUE;
}

void freeList(block *ptr) {
    if (checkAllFree()) {
        if (brk(head) == BRK_FAILED) {
            exit(1);
        }
        head = NULL;
    }
}

void merge(void) {
    block *href = head;

    while (href && href->next_) {
        if (href->free_ && href->next_->free_) {
            href->size_ += href->next_->size_;
            href->next_ = href->next_->next_;
            href->next_->previouse_ = href;
        }
        href = href->next_;
    }
}

void shrinkHeap(void) {
    block *href = head;

    if (href) {
        while (href->next_) {
            href = href->next_;
        }
        if (href->free_) {
            if (href->previouse_ != NULL) {
                href->previouse_->next_ = NULL;
            }
            if (brk(href) == BRK_FAILED) {
                exit(1);
            }
        }
    }
}

void *malloc(size_t size) {
    if (!size) {
        return NULL;
    }
    pthread_mutex_lock(&mutex);

    block *new_list = findExactSizeMatch(size);
    if (new_list == NULL) {
        new_list = findLargerSize(size);
    }
    if (new_list == NULL) {
        new_list = allocateMemory(size);
    }
    pthread_mutex_unlock(&mutex);
    if (new_list)
        return new_list += 1;
    else
        return NULL;
}

void free(void *ptr) {
    if (!ptr || !head) {
        return;
    }
    pthread_mutex_lock(&mutex);

    block *pref = ptr;
    pref -= 1;
    pref->free_ = TRUE;

    freeList(pref);
    merge();
    shrinkHeap();

    pthread_mutex_unlock(&mutex);
}