This project is a custom memory allocator implemented using a double linked list data structure. The allocator was developed as a learning exercise to better understand how the standard malloc library works.
By creating my own version of the memory allocation functionality, I was able to experiment with different strategies, test the allocator's performance across various programs and gain deeper understanding of the underlying mechanisms involved.
- Double Linked List-based Allocation: The allocator maintains a double linked list of free memory blocks to optimize allocation and deallocation times.
- Best-Fit Allocation: When allocating memory, the allocator uses a "best-fit" strategy to select the most suitable free block, reducing memory fragmentation.
- Automatic Memory Coalescing: Neighboring free blocks are automatically merged to prevent fragmentation and improve utilization of available memory.
- Automatic Memory Unmapping: When a page is no longer in use, the allocator unmap it to save space.
- Checksumming and Corruption Detection: The allocator calculates and stores checksums for each memory block to detect and prevent memory corruption issues.
- Multithreading Support: A mutex is used to ensure thread-safe operation of the allocator, allowing it to be used in concurrent applications.
- Alignment: All returned addresses are aligned to the
sizeof(double long)to make operations faster. - Debugging Tools: The
utilities.cfile contains a lot of functions that can be used to debug issues, you can for example print a clean looking representation of the current memory.
- The allocator appears to have issues when used with the GIMP image editor application. Further investigation is required to determine the root cause of this problem.
The allocator can be used as a drop-in replacement for the standard malloc library by linking against the libmalloc.so shared library (run make library to compile). A comprehensive test suite has been developed to validate the allocator's functionality across a wide range of scenarios.
To run the test suite, run make check. The output will display the results of the various tests, including any failures or issues encountered.
It can be used to run smoothly Chromium for example, or some CLI program such as ls, git status, tree, ip a, ...
If you have any suggestions or ideas for improving the allocator, or if you've discovered a fix for the GIMP compatibility issue, I would greatly appreciate your feedback. Please feel free to submit a pull request or open an issue in the project repository.
This project was developed by Fayçal Beghalia. Any use of this code is authorized, provided that proper credit is given.
This library can be compiled using itself, to do so: run make library then LD_PRELOAD=./libmalloc.so make library.
Testuite Output
┌───────────────────────────────────────────────────┐
│ Malloc Test Script │
├──────┬────────────────────────────────────────────┤
│ OK │ factor 20 30 40 50 60 70 80 90 │
├──────┼────────────────────────────────────────────┤
│ OK │ cat tests/testsuite.sh │
├──────┼────────────────────────────────────────────┤
│ OK │ ip a │
├──────┼────────────────────────────────────────────┤
│ OK │ ls │
├──────┼────────────────────────────────────────────┤
│ OK │ ls -la │
├──────┼────────────────────────────────────────────┤
│ OK │ find ../ │
├──────┼────────────────────────────────────────────┤
│ OK │ tree ../ │
├──────┼────────────────────────────────────────────┤
│ OK │ od ./libmalloc.so │
├──────┼────────────────────────────────────────────┤
│ OK │ git status │
├──────┼────────────────────────────────────────────┤
│ FAIL │ gimp --version │
├──────┼────────────────────────────────────────────┤
│ OK │ chromium --version │
├──────┴────────────────────────────────────────────┤
│ Total: 10 / 11 Tests Successful │
└───────────────────────────────────────────────────┘
A snapshot file generated by utilities_blka_snapshot(1)
┏━━━━━━━━━━━━━━━━╸ ALLOCATOR ╺━━━━━━━━━━━━━━━━┓
┃ Address : 0x7f48996a0000 ┃
┃ Address Aligned : Yes ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Meta : 0x7f48996a0040 ┃
┃ Free List : 0x7f48996a0470 ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Blocks : 3 ┃
┃ Free Blocks : 1 ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Size (bytes) : 4096 ┃
┃ Size Valid : Yes ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ List Valid : Yes ┃
┃ Free List Valid : Yes ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
┏━━━━━━━━━━━━━━━━━━━╸START╺━━━━━━━━━━━━━━━━━━━┓
┃ Address : 0x7f48996a0040 ┃
┃ Address Aligned : Yes ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Index : 0 ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Free : No ┃
┃ Size (bytes) : 1008 ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Next : 0x7f48996a0470 ┃
┃ Prev : (nil) ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Next Free : (nil) ┃
┃ Prev Free : (nil) ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Checksum : 817 ┃
┃ Checksum Valid : Yes ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Data : 0x7f48996a0080 ┃
┃ Data Aligned : Yes ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Garbage : 0 ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
⇅
┏━━━━━━━━━━━━━━━━━━━╸BLOCK╺━━━━━━━━━━━━━━━━━━━┓
┃ Address : 0x7f48996a0470 ┃
┃ Address Aligned : Yes ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Index : 1 ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Free : Yes ┃
┃ Size (bytes) : 2832 ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Next : 0x7f48996a0fc0 ┃
┃ Prev : 0x7f48996a0040 ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Next Free : (nil) ┃
┃ Prev Free : (nil) ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Checksum : 1215 ┃
┃ Checksum Valid : Yes ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Data : 0x7f48996a04b0 ┃
┃ Data Aligned : Yes ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Garbage : 0 ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
⇅
┏━━━━━━━━━━━━━━━━━━━━╸END╺━━━━━━━━━━━━━━━━━━━━┓
┃ Address : 0x7f48996a0fc0 ┃
┃ Address Aligned : Yes ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Index : 2 ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Free : No ┃
┃ Size (bytes) : 0 ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Next : (nil) ┃
┃ Prev : 0x7f48996a0470 ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Next Free : (nil) ┃
┃ Prev Free : (nil) ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Checksum : 590 ┃
┃ Checksum Valid : Yes ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Data : 0x7f48996a1000 ┃
┃ Data Aligned : Yes ┃
┠╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┨
┃ Garbage : 4096 ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛