Malloc - 42Born2Code

Challenge

A dynamic zone memory allocator based on the buddy system.

The goal is to implement a memory allocator that manages blocks inside pre-allocated zones.

The implemented functions are: malloc(), realloc(), calloc(), free(), show_alloc_mem() and show_alloc_mem_hex(). All of them use a mutex lock in order to be thread-safe.

Zones management

The allocator keeps track of the zones with a linked list, each zone implements a binary buddy system that manages the blocks.

There are three types of zones:

1. Tiny for blocks with size less than or equal to TINY_THRESHOLD.
2. Small for blocks with size between TINY_THRESHOLD + 1 and SMALL_THRESHOLD included.
3. Large for blocks with size larger than SMALL_THRESHOLD.

The Large zone does not implement a buddy system, each block has a dedicated zone.

A zone with a buddy system can contain at least 100 of its biggest blocks.

The zone size is always multiple of the system page size.

Buddy system

The binary buddy system uses blocks that are only power of 2.

Each block has a header of 16 bytes that contains some metadata.

 __Block_header______Payload_________
|_______________|____________________|   the payload is the usable part of the block,
0            16 bytes                    its size depends on the request.
                ^
                |____ address returned to the user (e.g. the returned value of malloc).

The addresses of the blocks as well as the addresses returned to the user are 16-bytes aligned.

During a block request, for example, by calling malloc(requested_size), the allocator follows these steps:

1. Round the requested_size up to a power of 2, let's call it rounded_size.
2. Find a free block that is the closest to the rounded_size.
3. Split the free block into smaller blocks until it has a size equal to rounded_size.
4. Return the payload of the free block.

Blocks arrangement (source: http://homepage.divms.uiowa.edu/~jones/opsys/notes/27.shtml)

The buddy allocator arranges things so that blocks of size 2^N always begin at memory addresses where the N least significant bits are zero.

For example:

• blocks of size 2^0 can begin at any address.
• blocks of size 2^1 can only begin at even addresses (least significant bit equals zero).
• blocks of size 2^2 can only begin at addresses with the least significant 2 bits equal to zero.

The constraints on the block addresses have an important consequence: when a block of size 2^(N + 1) is split into two blocks of size 2^N, the addresses of these two blocks will differ in exactly one bit, bit N. Thus, given a block, we can easily calculate the address of its buddy.

This operation is implemented with the BUDDY macro.

Buddy calculation examples:

Size	Address in decimal	Buddy's address in decimal	Address in binary	Buddy's address in binary
512(2^9)	0	512	0000000000000000	0000001000000000
64(2^6)	192	128	0000000011000000	0000000010000000
32(2^5)	224	192	0000000011100000	0000000011000000

Malloc and free examples

Let's start with an empty memory of 128 bytes.

            ________________________
 Legend:   |______|+++++++++++++++++|
             free      allocated
                   (header + payload)
 _______________________________________________________________
|_______________________________________________________________|
0                                                              128
 _______________________________________________________________
|+++++++++++++++|_______________________________________________|   p1 = malloc(10);
0               32                                             128
 _______________________________________________________________
|+++++++++++++++|_______________|+++++++++++++++++++++++++++++++|   p2 = malloc(40);
0               32              64                             128
 _______________________________________________________________
|+++++++++++++++|+++++++++++++++|+++++++++++++++++++++++++++++++|   p3 = malloc(14);
0               32              64                             128
 _______________________________________________________________  
|_______________________________|+++++++++++++++++++++++++++++++|   free(p1); free(p3);
0                               64                             128
 _______________________________________________________________
|_______________________________________________________________|   free(p2);
0                                                              128

For more details look at the subject.

Using the project

git clone --recursive https://github.com/fedefloris/Malloc.git && cd Malloc && make

Now you should see libft_malloc.so in the root folder.

gcc your_file.c libft_malloc.so -I includes -I libft/includes

Example of your_file.c:

#include "malloc.h"

int     main(void)
{
  void  *ptr;

  if (!(ptr = malloc(15)))
    ft_printf("malloc call failed\n");
  // ...
  // use ptr
  // ...
  free(ptr);
  return (0);
}

Unless you copy the library into one of the standard directories (e.g., /usr/lib) you need to specify the location of libft_malloc.so.

On Linux you can use LD_LIBRARY_PATH.

export LD_LIBRARY_PATH=$(pwd):$LD_LIBRARY_PATH

You could also use LD_PRELOAD to run programs with libft_malloc.so implementations of malloc(), realloc(), calloc() and free().

LD_PRELOAD=./libft_malloc.so ls
LD_PRELOAD=./libft_malloc.so vim Makefile

Running the tests

make tests

License

This project is licensed under the MIT License - see the LICENSE.md file for details