Malloc tutorial
Visit WebsitePatreon
Unknown
Summary
This Patreon page provides a tutorial on how to write a malloc implementation in C. It explains the basics of memory allocation, how malloc and free work, and how to implement them using sbrk. The tutorial covers concepts like storing meta-information about memory regions, using a linked list to track free blocks, and implementing realloc and calloc. It also includes debugging tips using gdb and exercises for further learning. The post also provides instructions on how to compile the code and use the custom malloc implementation with existing binaries, along with debugging techniques and exercises for further exploration.
Content Sections
Malloc tutorial
This tutorial explains how to write a malloc implementation in C, covering concepts like sbrk, storing meta-information, using a linked list for free blocks, and implementing realloc and calloc. It includes code examples and debugging tips.
Preliminaries
The tutorial assumes familiarity with pointers, C syntax, malloc, and linked lists. It uses sbrk to manipulate the heap, incrementing the heap size to allocate memory.
Simple Malloc Implementation
A basic malloc implementation using sbrk is presented, which increments the heap size and returns a pointer to the new region. This implementation lacks thread safety and does not handle free.
Free Implementation
The tutorial explains how free works by storing meta-information about memory regions just below the returned pointer. A single linked list is used to track free blocks.
Block Meta Structure
A struct block_meta is defined to store the size, next block, free status, and a magic number for debugging.
Find Free Block
The find_free_block function iterates through the linked list to find a free block that is large enough for the requested size.
Request Space
The request_space function requests space from the OS using sbrk, adding extra space for the block_meta struct and setting the struct's fields.
Malloc Implementation with Free Space Reuse
The malloc function checks for existing free space and reuses it if possible. If no free space is available, it requests new space using sbrk.
Free Implementation Details
The free function sets the ->free flag for a block and includes assertions to help with debugging. It also defines a get_block_ptr function to retrieve the block_meta pointer from a given pointer.
Realloc and Calloc
The tutorial implements realloc, which adjusts the size of a block, and calloc, which allocates memory and initializes it to 0.
Using Custom Malloc with Existing Programs
Instructions are provided on how to compile the code and use the custom malloc implementation with existing binaries using LD_PRELOAD on Linux and DYLD_INSERT_LIBRARIES on macOS.
Debugging
Debugging tips using gdb are provided, including how to set breakpoints, inspect memory, and step through code. Examples of debugging common errors are given.
Exercises
Exercises are provided for the reader to improve the malloc implementation, including fixing alignment, implementing block splitting, merging adjacent free blocks, and finding bugs.
Resources
Links to additional resources are provided, including other malloc tutorials, information on Linux memory management, and real-world malloc implementations like dlmalloc, tcmalloc, and jemalloc. Address Sanitizer and Thread Sanitizer are mentioned for debugging.
Acknowledgements
Thanks are given to various individuals for their contributions and feedback.