malloc
realloc
calloc
free

A C dynamic memory allocation implementation from @ezalos, @rkirszba and @arobion


· Report Bug ·

Table of Contents

• About the Project
  • Built With
• Getting Started
  • Prerequisites
  • Installation
• Usage
• Architecture
  • Structures
• Resources
• License

About The Project

As part of our learning at 42 we decided to re-implement malloc, realloc, calloc and free.

void	*malloc(size_t size);

void	*realloc(void *ptr, size_t size);

void	*calloc(size_t count, size_t size);

void	free(void *ptr);

📖 Subject 📖

C dynamic memory allocation refers to performing manual memory management for dynamic memory allocation in the C programming language via a group of functions in the C standard library, namely malloc, realloc, calloc and free.

Here's why we are proud of our work:

• 🚀 This implementation focus on having good performances in speed of execution.

• 💻 Our implementation is multi-threading compatible!

• 🌱 We have very little depedencies, almost everything has been recoded from scratch. Here's the full list of the function we didn't coded ourselves in this project:

  • mmap
  • munmap
  • write
  • And, for the multi-threading compatibility, the functions of lib pthread

Getting Started

This is an example of how you may give instructions on setting up your project locally. To get a local copy up and running follow these simple example steps.

Prerequisites

For this project you need to have installed on your computer

• git
• gcc
• make

Installation

1. Clone the repo

   git clone https://github.com/ezalos/malloc.git
   cd malloc

2. Build the dynamic library

   make

3. Run the testings

   make tests

Usage

As this program create a dynamic library, we need to ask the Operating System to use our work instead of the implementation in libc. For doing so, we give instructions during the loading of the program.

• Linux:

   LD_PRELOAD="libft_malloc.so" HUGETLB_MORECORE=yes your_program.out

• MacOS:

    DYLD_LIBRARY_PATH=. DYLD_INSERT_LIBRARIES="libft_malloc.so" DYLD_FORCE_FLAT_NAMESPACE=1 your_program.out

  With the last security update on MacOS, you might need to follow this setup.

Architecture

Low level Structures

There is different levels of memory used in this project, from the smallest unit, to the largest:

• allocation:

  It's the memory delivered to the user.

  Each allocation given by malloc is preceded by an header:

  typedef	struct				s_alloc_header
  {
   /*custom structure for a node of red black tree*/
  	t_rbt					rbt;
   /*size of the memory following this header*/
  	uint32_t				size;
   /*size of the preceding memory*/
  	uint32_t				size_prev;
   /*see below*/
  	uint8_t					flags;
  }							t_alloc_header;

  This flags variable contains multiple informations encoded:

  • Position
    • Is it the first allocation of zone
    • Is it the last allocation of zone
  • Availability
    • Is this allocation available to use
  • Zone type
    • Is this allocation in a large zone
    • Is this allocation in a small zone
    • Is this allocation in a tiny zone

  Each allocation is followed by size octets

• Zones:

  Zones are large chunks of continuous memory delivered by mmap. Inside a zone, we find a succession allocation header, followed by the corresponding size of dedicated memory.

  Each zone is preceded by an header:

  typedef	struct				s_zone_header
  {
  	struct s_zone			*next_zone;
  	struct s_zone			*prev_zone;
  	size_t					size;
  }							t_zone_header;

  Zones are linked together by mem_type inside a double linked list.

  Here is a representation of a zone:

[header_zone][header_alloc][xxxxxxxxxxxxxxxxxxxxxxx][header_alloc][xxxxxxxxx
xxxxxxxxxxxxxxxxxxxx][header_alloc][oooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooo][header_alloc][xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxx][header_alloc][ooooooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo]

• Legend:

  • with t_zone_header -> [header_zone]
  • with t_alloc_header -> [header_alloc]
  • with used memory -> [x]
  • with free memory -> [o]

• mem_type:

mem_types are a collection of zones, which are grouped inside a double linked list.

We make the difference between three types of mem_types, depending of the size of allocation asked by user.

 * **Tiny**

	It's allocations sizes ranges from 0 octets to 1024 octets.

	They have a resolution of 16 octets.
	resolution means that we complete them to be a multiple of 16, as in the libc implementation of malloc.

 * **Small**

   It's allocations sizes ranges from 1024 octets to 16MB.

   They have a resolution of 512 octets.


 * **Large**

   It's allocations sizes ranges from 0 octets to 1024 octets.

   They have a resolution of 4096 octets.

Resources

• man pages
  • mmap and munmap: 🔗
  • malloc, realloc, calloc and free: 🔗
• A detailled architecture of malloc libc: 🔗

License

Distributed under the WTFPL LICENSE. See LICENSE for more information.