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

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 size)
    {
      g_list->is_used = USED;
      return (g_list->addr);
    }
  while(g_list->head != 1)
    {
      if (g_list->is_used == UNUSED && size 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 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"

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:

-
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.

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

-
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:

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

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

-
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:

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

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

1. Review

I just reviewed malloc.c and malloc.h.

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

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

-
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.

-
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.

-
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)

-
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 *)

-
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.

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

#define SBRK_FAILED ((void *)-1)

-
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.

-
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.

-
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.

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

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

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

StackExchange Code Review Q#80190, answer score: 17