malloc(), free(), realloc() using brk() and sbrk()

Question

I recoded malloc() by using brk() and sbrk(). I just want some "reviews" to see if it is possible to improve my code to make it faster and better. If I'm doing some tests like "ls -Rla /" it takes a lot longer than the original ls, and if I do with "sh -c", it's way longer than the first one.

malloc.c

#include "../inc/malloc.h"

t_list      *g_list;

void        *malloc(size_t size)
{
  void      *addr;
  static int    i = 0;

  if (size == 0)
    return (NULL);
  size = (size - 1) / 4 * 4 + 4;
  addr = find_block(size);
  if (addr != NULL)
    {
      re_init_list();
      return (addr);
    }
  addr = sbrk(size);
  if (addr == (void *)-1)
    {
      printf("Error : sbrk() failed\n");
      return (NULL);
    }
  if (i == 0)
    g_list = NULL;
  put_in_list(&g_list, size, addr);
  ++i;
  return (addr);
}

void        *find_block(size_t size)
{
  if (g_list == NULL)
    return (NULL);
  if (g_list->is_used == UNUSED && size <= g_list->size)
    {
      g_list->is_used = USED;
      return (g_list->addr);
    }
  while(g_list->head != 1)
    {
      if (g_list->is_used == UNUSED && size <= g_list->size)
    {
      g_list->is_used = USED;
      return (g_list->addr);
    }
      g_list = g_list->next;
    }
  re_init_list();
  return (NULL);
}

realloc.c

#include "../inc/malloc.h"

extern t_list   *g_list;

void        *realloc(void *ptr, size_t size)
{
  void      *cpy;
  size_t    ptr_size;

  if (size == 0 && ptr != NULL)
    {
      free(ptr);
      return (ptr);
    }
  else if (ptr == NULL || is_in_list(ptr) == 1)
    ptr = malloc(size);
  else
    {
      ptr_size = get_size(ptr);
      if (ptr_size == size)
        return (ptr);
      cpy = malloc(size);
      if (size < ptr_size)
        memcpy(cpy, ptr, size);
      else
        memcpy(cpy, ptr, ptr_size);
      free(ptr);
      return (cpy);
    }
  return (ptr);
}

int is_in_list(void *ptr)
{
  t_list    *tmp;

  tmp = g_list;
  while (tmp->addr != ptr && tmp->head != 1)
    tmp = tmp->next;
  if (tmp->addr != ptr)
    return (1);
  return (0);
}

size_t      get_size(void *ptr)
{
  t_list    *tmp;

  tmp = g_list;
  while (tmp->addr != ptr)
    tmp = tmp->next;
  return (tmp->size);
}

free.c

#include "../inc/malloc.h"

extern t_list   *g_list;

void    free(void *ptr)
{
  if (ptr == NULL)
    return ;
  if (is_in_list(ptr) == 1)
    return ;
  while (ptr != g_list->addr && g_list->head != 1)
    g_list = g_list->next;
  if (g_list->is_used == UNUSED)
    return ;
  g_list->is_used = UNUSED;
  if (g_list->head != 1)
    {
      if (g_list->next->is_used == UNUSED &&
      g_list->next->addr != g_list->addr)
    {
      if (g_list->addr > g_list->next->addr)
        g_list->addr = g_list->next->addr;
      g_list->head = g_list->next->head;
      g_list->size += g_list->next->size;
      g_list->next = g_list->next->next;
    }
    }
  re_init_list();
}

list.c

#include "../inc/malloc.h"

extern t_list   *g_list;

void        put_in_list(t_list **list, size_t size, void *addr)
{
  t_list    *tmp;

  tmp = sbrk(sizeof(*tmp));
  if (tmp == (void *)-1)
    {
      printf("Error : sbrk() failed\n");
      return ;
    }
  tmp->size = size;
  tmp->is_used = USED;
  tmp->addr = addr;
  if (*list == NULL)
    tmp->head = 1;
  else
    {
      tmp->head = 0;
      tmp->next = *list;
      if (tmp->next)
    tmp->next->prev = tmp;
    }
  *list = tmp;
  make_circle(list);
}

void        make_circle(t_list **list)
{
  t_list    *tmp;

  tmp = *list;
  while ((*list)->head != 1)
    (*list) = (*list)->next;
  (*list)->next = tmp;
  (*list)->next->prev = *list;
  while ((*list) != tmp)
    *list = (*list)->next;
}

void    re_init_list()
{
  while (g_list->head != 1)
    g_list = g_list->next;
  g_list = g_list->next;
}

malloc.h

#ifndef MALLOC_H_
# define MALLOC_H_

# include <unistd.h>
# include <string.h>
# include <stdio.h>

# define UNUSED 0
# define USED   1

typedef struct  s_list
{
  size_t    size;
  int       is_used;
  void      *addr;
  int       head;
  struct s_list *prev;
  struct s_list *next;
}       t_list;

void    *malloc(size_t size);
void    put_in_list(t_list **list, size_t size, void *addr);
void    free(void *ptr);
void    make_circle(t_list **list);
void    show_alloc_mem();
void    *realloc(void *ptr, size_t size);
size_t  get_size(void *ptr);
void    re_init_list();
void    *find_block(size_t size);
int is_in_list(void *ptr);

#endif /* !MALLOC_H_ */

Answer 1

1. Performance

This memory management implementation maintains a single doubly-linked list of memory blocks. The main causes of the performance problems are as follows:

1. When malloc is called, the global pointer to the list is needlessly updated (see §2.18 below) and then the whole list is traversed in order to find the start of the list again.

2. Allocated blocks are not removed from the list, so malloc has to uselessly examine all the allocated blocks each time it is called.

3. When free is called, the whole list might need to be traversed in order to find the block containing the freed memory.

The result is that every memory operation might need to look at all the memory blocks. Any program using this implementation therefore runs in quadratic time (or worse).

To fix these problems:

1. Don't update the global pointer, use a local variable to remember the position in the list. (See §2.18.)

2. Remove blocks from the list when they are allocated and insert them when freed. (Thus making the list into a free block chain.)

3. Design a mechanism that finds the s_list structure corresponding to an allocated address in constant time. For example, if each s_list structure is placed in memory immediately below the allocated block, then it can be found by subtracting sizeof(s_list) from the freed address.

The result will be better, but still won't be all that good, because of the following problems:

1. There's no segregation of blocks, so no quick way of finding a free block of the requested size.

2. The list structures are large (six words), so a program that allocates many small objects will suffer from internal fragmentation.

2. Review

I just reviewed malloc.c and malloc.h.

1. The code is not thread-safe so cannot be used in multi-threaded programs.

2. The global variable g_list needs a comment. What is this?

3. This line needs explanation:

   size = (size - 1) / 4 * 4 + 4;
   

   Presumably the intention is to align size up to the next multiple of 4. But you should make that clear with a comment.

4. Aligning upwards to a multiple of a power of 2 is better done like this:

   /* Align upwards to next multiple of 4. */
   size = (size + 3) & ~3;
   

   This has two arithmetic operations instead of four.

5. Where does the number 4 come from? A constant like this needs a name. Presumably it's the maximum required alignment for any object that might be allocated with malloc, so you need something like:

   /* Alignment of allocated addresses, in bytes. */
   #define ALIGNMENT (4)
   

6. It's unlikely that the alignment requirement is actually 4. On x86-64, long, double, and pointer types should be 8-byte aligned. To make the code portable, you probably want something like:

   /* Alignment of allocated addresses, in bytes. */
   #define ALIGNMENT sizeof(void *)
   

7. sbrk is a "LEGACY" interface according to POSIX: that is, it should be avoided in new programs. In addition:

   The behaviour of brk() and sbrk() is unspecified if an application also uses any other memory functions (such as malloc(), mmap(), free()). Other functions may use these other memory functions silently.

   The modern way to ask a Unix operating system to give you a range of virtual memory addresses is to call mmap, passing MAP_ANONYMOUS (on Linux) or MAP_ANON (on BSD):

   void *addr = mmap(0, size, PROT_READ | PROT_WRITE,
                     MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
   if (addr == MAP_FAILED) {
       /* handle the error */
   }
   

   mmap allocates memory in units of pages, which are typically 4 KB in size. So a malloc implementation needs to map memory in page-sized (or larger) chunks, and then split the chunks up as needed.

8. The constant (void *)-1 needs a name. I would write:

   #define SBRK_FAILED ((void *)-1)
   

9. If sbrk fails then malloc prints an error message to standard output. This is a bad idea. It's not the job of malloc to output error messages: it should just return NULL and let the caller handle the error. But if you are going to emit an error message, it should go to the standard error stream, not standard output.

10. The logic for initializing g_list is in malloc:

    if (i == 0)
      g_list = NULL;
    

    but this is pointless, since you could have just initialized g_list = NULL; in the first place.

11. Each time malloc is called, the variable i is incremented. But i is an int, which on many systems has a maximum value of 2,147,483,647. So after this many allocations, there will be a signed integer overflow, which has undefined behaviour. Better to just set i = 1, which can't go wrong like that.

12. The functions that are not defined by POSIX (find_block, re_init_list, etc.) need comments explaining what they do.

13. The data structure s_list needs comments explaining the meaning of each of its members.

14. The declaration extern t_list *g_list; should go in the header, so that you don't have to repeat it in each source file.

15. It would be better to #include <stdlib.h> to get the standard prototypes for malloc, realloc and free.

16. If you're going to define malloc, realloc and free, then you should define calloc too, otherwise a program might call the calloc from the standard C library and then pass the pointer to your free.

17. In C, the number 0 tests false and any other number tests true. So there's no need to define constants UNUSED and USED, or to compare against these. You can just write:

    if (g_list->is_used && size <= g_list->size)
    

    And similarly:

    while(!g_list->head)
    

18. The loop in find_block updates the global value of g_list as it searches the linked list. Then you call re_init_list to set g_list back to the start of the list again. So why did you update it in the first place?? It would be better to use a local variable to remember your position in the list:

    t_list *cur = g_list; /* current position in the list */
    do {
        if (!cur->is_used && size <= cur->size) {
            cur->is_used = 1;
            return cur->addr;
        }
        cur = cur->next;
    } while (cur != g_list);
    

    Notice that in this version of the code we don't have to consult head at all. If you made similar changes throughout then you'd be able to get rid of the head member of the stucture.