mfunyu / malloc Goto Github PK

View Code? Open in Web Editor NEW

2.0 2.0 0.0 355 KB

Find out the workings behind optimum memory management and recode it, as well as free and realloc.

Makefile 8.17% C 66.25% CMake 1.24% Shell 1.87% C++ 14.71% Python 7.76%

42cursus 42second-circle

malloc's Introduction

🦒 mfunyu

malloc's People

Contributors

Stargazers

Watchers

malloc's Issues

[bug] SMALL block un-freed when exceed MAX size by alignment

else if (size <= SMALL_MAX)
		_free_alloc(&(g_malloc.small_magazine), chunk);

remove size classifications

[crush] with unmalloced call to free

$> LD_PRELOAD=./libft_malloc.so MallocDebug=1 bash
[ malloc]                 : malloc(6) = 0x7f5212f25300
[ malloc]                 : malloc(6) = 0x7f5212f25320
[ malloc] by hash_insert  : malloc(32) = 0x7f5212f25340
[ malloc] by make_variable_value : malloc(3) = 0x7f5212f25370
[ malloc]                 : malloc(48) = 0x7f5212f25390
[ malloc]                 : malloc(8) = 0x7f5212f253d0
[ malloc]                 : malloc(8) = 0x7f5212f253f0
[ malloc] by hash_insert  : malloc(32) = 0x7f5212f25410
[ malloc] by make_variable_value : malloc(3) = 0x7f5212f25440
[ malloc] by _rl_init_terminal_io : malloc(2032) = 0x7f520cbeec10
[ malloc] by _rl_init_terminal_io : malloc(4080) = 0x7f520cbef410
[ malloc] by __strdup     : malloc(15) = 0x7f5212f25460
[ malloc] by _nc_home_terminfo : malloc(25) = 0x7f5212f25480
[ malloc] by __strdup     : malloc(13) = 0x7f5212f254b0
[ malloc] by _nc_first_db : malloc(94) = 0x7f5212f254d0
[   free] by _nc_read_entry2 : free(0x558795f0c610)
[1]    47934 segmentation fault (core dumped)  LD_PRELOAD=./libft_malloc.so MallocDebug=1 bash

[bug] inf loop on many mallocs

$> ./test/run_benchmark.sh

===== test11: time overhead =====
1 loops of 1000 mallocs and 500 free
-> 1000 mallocs, 500 frees

real    0m0.005s
user    0m0.002s
sys     0m0.000s

===== test11: time overhead =====
10 loops of 1000 mallocs and 500 free
-> 10000 mallocs, 5000 frees

real    0m0.017s
user    0m0.011s
sys     0m0.000s

===== test11: time overhead =====
100 loops of 1000 mallocs and 500 free
-> 100000 mallocs, 50000 frees
^C

[change] use top for unused block

An unused chunk is also considered as free block now
store top value and treat differently.

[impl] last free cache

unsorted bin freellist[1]

[segfault] bug negative chunk size crash

$> MallocShowAbbr=1 LD_PRELOAD=./libft_malloc.so LD_LIBRARY_PATH=. ./correction 3 2> file

 0x7ff23232bf30   ||       0xffffffffffffff71 | prev_size
------------------++--------------------------+
�[m 0x7ff23232bf38   || 842179328 (0x7ff23232a308) |-|-| size
------------------++--------------------------+
 0x7ff23232bf40   ||                      0x0 | fd
------------------++--------------------------+
 0x7ff23232bf48   ||                      0x0 | bk
------------------++--------------------------+
 0x7ff23232bf50   ||                          | 
                  || [ 842179304 (0x7ff23232a2e8)] |
==================++==========================+

[segfault] realloc extending

    Start 1: ReallocTest.Expanding
1/1 Test #1: ReallocTest.Expanding ............***Exception: SegFault  0.18 sec

0% tests passed, 1 tests failed out of 1

Total Test time (real) =   0.19 sec

The following tests FAILED:
          1 - ReallocTest.Expanding (SEGFAULT)

< FreeList >
----------------+----------------+----------------+----------------+
 0x7ff29c9b4018 |     8 (   0x8) | 0x7ff29c9b4028 |         0x5fc0 |
----------------+----------------+----------------+----------------+
 0x7ff29c9b4028 | 24504 (0x5fb8) |            0x0 | 0x7ff29c9b4018 |
----------------+----------------+----------------+----------------+

[impl] heap extention

[crush] unexpected index size

$> MallocDebug=1 make test
...
[ RUN      ] MallocSmallTest.FillUp
make: *** [Makefile:139: test] Error 139

 = 0x7fe6b0509410
[ malloc]                 : malloc(100352)size: 100352
chunk_size: 100864
largebin_index
chunk2: 0x0
top: 0x7fe6b0521c00
chunk4: 0x7fe6b0521c00
chunk5: 0x7fe6b0521c00
chunk3: 0x7fe6b0521c00
 = 0x7fe6b0521c10
[ malloc]                 : malloc(100379)size: 100379
chunk_size: 100864
largebin_index
chunk2: 0x0
top: 0x7fe6b053a600
chunk4: 0x7fe6b053a600
freelist_add
chunk_size: 35296
index: 2204
Segmentation fault (core dumped)

[segfault] malloc a lot in tiny region and it crushes

#include <stdio.h>
#include <string.h>
#include "malloc.h"
#include "ft_printf.h"

void	malloc_alot()
{
	void	*ptr[104];
	for (int i = 0; i < 104; i++)
		ptr[i] = malloc(1000);
	ptr[2] = malloc(570);
}

int main()
{
	ft_printf("=== test5 use up malloc ===\n");

	malloc_alot();
	malloc(150);
	malloc(1);
	malloc(1);
}

[bug] google test crush

$> make test
cd ./test/googletest && cmake --build build 1> /dev/null
CMake Error at /usr/share/cmake-3.22/Modules/GoogleTestAddTests.cmake:83 (message):
  Error running test executable.

    Path: '/nfs/homes/mfunyu/sgoinfre/42/malloc/test/googletest/build/test_malloc'
    Result: Segmentation fault
    Output:
      Running main() from /nfs/homes/mfunyu/sgoinfre/42/malloc/test/googletest/build/_deps/googletest-src/googletest/src/gtest_main.cc
      MallocTinyTest.
        One
        SameMultiple
        DiffMultiple
        Small
        BigMultiple
        OverLimit
      MallocSmallTest.
        One
        SameMultiple
        DiffMultiple
        BigMultiple
        FillUp
      MallocLargeTest.
        One
        OneFree
        BigMultiple
      MallocFreeTest.
        Zero
      ErrorTest.
        Malloc
      ReallocTest.
        SameSize
        SameAlignedSize
        EdgeSize
        Expanding
        Realloced
        NullZero
        ReserveContents
      

Call Stack (most recent call first):
  /usr/share/cmake-3.22/Modules/GoogleTestAddTests.cmake:179 (gtest_discover_tests_impl)


gmake[3]: *** [CMakeFiles/test_malloc.dir/build.make:116: test_malloc] Error 1
gmake[3]: *** Deleting file 'test_malloc'
gmake[2]: *** [CMakeFiles/Makefile2:137: CMakeFiles/test_malloc.dir/all] Error 2
gmake[1]: *** [Makefile:146: all] Error 2
make: *** [Makefile:139: g_build] Error 2

[segfault] many large allocations

TEST(MallocLargeTest, BigMultiple) {
	TestMultiple(1040384, 100, true);
}

[fix] O(n) in free

[error] magazine->top = 0x0, Error: pointer being freed was not allocated

$> LD_PRELOAD=./libft_malloc.so MallocDebug=1 git
[ malloc] by _IO_file_doallocate : malloc(4096) = 0x7fe1bff01610
[realloc]                 : realloc(0x0, 1600) = 0x7fe1bff02810
[realloc]                 : realloc(0x0, 1024)allocating tiny
 = 0x7fe1c623b480
[realloc]                 : realloc(0x7fe1c623b480, 2048)freeing tiny
magazine->top: 0x0
Error: pointer being freed was not allocated
 = 0x7fe1bff03010
[   free] by _IO_setb     : free(0x7fe1bff01610)
[   free] by _IO_fclose   : free(0x7fe1c623b2a0)
freeing tiny
magazine->top: 0x0
Error: pointer being freed was not allocated
[ malloc]                 : malloc(5)allocating tiny
 = 0x7fe1bf9ae010
[ malloc]                 : malloc(54)allocating tiny
 = 0x7fe1bf9ae030
[ malloc]                 : malloc(168)allocating tiny
 = 0x7fe1bf9ae070
[ malloc]                 : malloc(49)allocating tiny

[crush] unterminated free

$>  LD_PRELOAD=./libft_malloc.so MallocDebug=1 gcc -I includes -I libft -I ft_printf -I . ./test/single_test/test2.c -L. -lft_malloc -Llibft -lft -Lft_printf -lftprintf -o single_test
...
[   free] by bfd_close_all_done : free(0x7fdbe762f980) -> terminated
[   free] by bfd_close_all_done : free(0x7fdbe762faf0) -> terminated
[ malloc] by _objalloc_alloc : malloc(4064) = 0x7fdbe7d94810
[ malloc] by _objalloc_alloc : malloc(4064) = 0x7fdbe7d95810
[ malloc] by _objalloc_alloc : malloc(4064) = 0x7fdbe7d96810
[ malloc] by bfd_get_full_section_contents : malloc(464) = 0x7fdbe762fd00
[ malloc] by _objalloc_alloc : malloc(32552) = 0x7fdbe7d97810
[   free] by bfd_elf_link_add_symbols : free(0x7fdbe762fd00) -> terminated
[ malloc] by bfd_elf_get_elf_syms : malloc(72552) = 0x7fdbe7cbac10
[ malloc] by bfd_elf_get_elf_syms : malloc(96736) = 0x7fdbe7d25a10
[   free] by bfd_elf_get_elf_syms : free(0x7fdbe7cbac10)[   free]                 : free(0x7f6e1a91b2d0) -> terminated
[   free]                 : free(0x7f6e1a91b2f0) -> terminated
[   free]                 : free(0x7f6e1a91b230) -> terminated
[ malloc]                 : malloc(50) = 0x7f6e1a91a060
[   free]                 : free(0x7f6e1a91a060) -> terminated
[ malloc]                 : malloc(5) = 0x7f6e1a91b310
...
collect2: fatal error: ld terminated with signal 11 [Segmentation fault], core dumped

[fix] alignment 0xaaa0

align 16

[error] some addresses are considered as not allocated

$> ./tests/benchmark.sh
===== Benchmark-tiny: time overhead =====
10000 loops of 1000 mallocs and 500 free
-> 10000000 mallocs, 5000000 frees
size: 1056
chunk: 0x7f31cd8a6bc0
Error: ppp pointer being freed was not allocated
size: 1056
chunk: 0x7f31b8a34bc0
Error: ppp pointer being freed was not allocated
size: 1056
chunk: 0x7f319f23abc0
Error: ppp pointer being freed was not allocated
size: 1056
chunk: 0x7f319cd5cbc0
Error: ppp pointer being freed was not allocated

real	0m7.393s
user	0m4.178s
sys	0m0.758s

[impl] mmaped realloc

[crush] on gcc

$> LD_PRELOAD=./libft_malloc.so gcc main.c                             fix_review  ✱
collect2: fatal error: ld terminated with signal 11 [Segmentation fault], core dumped
compilation terminated.

[impl] freechunk sort

[imp] end of blocks (chunks)

Currently, there is no detection for the end of the blocks.
This will lead to an infinite loop in show_alloc_heap, and also make it impossible to tell the end of the mapped region.

[imp] merge free blocks

[impl] alignment validation

check alignment value
The alignment argument should be a power of two. If the argument is
not a power of two, the nearest greater power is used.

[crush] accessing invalid index

[ malloc] by _Znwm        : malloc(64) = 0x7f31ec1af9a0
[ malloc] by _Znwm        : malloc(132) = 0x7f31ec1af9f0
[ malloc] by _Znwm        : malloc(64) = 0x7f31ec1afa80
[ malloc] by _Znwm        : malloc(132) = 0x7f31ec1afad0
[   free]                 : free(0x7f31ec1af050)
index: 7
[   free]                 : free(0x7f31ec1aef30)
index: 7
[   free]                 : free(0x7f31ec1aee10)
index: 7
[   free]                 : free(0x7f31ec1aecf0)
index: 7
[   free]                 : free(0x7f31ec1aebd0)
index: 7
[   free]                 : free(0x7f31ec1aeab0)
index: 7
[   free]                 : free(0x7f31ec1ae990)
index: 7
[   free]                 : free(0x7f31ec1ae870)
index: 7
[   free]                 : free(0x7f31ec1ae750)
index: 7
[   free]                 : free(0x7f31ec1ae630)
index: 7
[   free]                 : free(0x7f31ec1ae510)
index: 7
[   free]                 : free(0x7f31ec1ae3f0)
index: 7
[   free]                 : free(0x7f31ec1aefc0)
index: 25
[   free]                 : free(0x7f31ec1aeea0)
index: 43
[   free]                 : free(0x7f31ec1aed80)
index: 61
[   free]                 : free(0x7f31ec1aec60)
index: 79
[   free]                 : free(0x7f31ec1aeb40)
index: 97
[   free]                 : free(0x7f31ec1aea20)
index: 115
[   free]                 : free(0x7f31ec1ae900)
index: 133
[   free]                 : free(0x7f31ec1ae7e0)
index: 151
[1]    330137 segmentation fault (core dumped)  LD_PRELOAD=./libft_malloc.so MallocDebug=1 clang

[bug] freelist block placed in a wrong size

	index = get_index_by_size(size);
	if (!freelist[index])
		return (NULL);
	chunk = freelist[index];
	if (CHUNKSIZE(chunk) > MIN_CHUNKSIZE + size)
	{
		SD("size", size);
		SD("index", index);
		SD("chunk", CHUNKSIZE(chunk));
		SP("chunk", chunk);
		show_alloc_mem_ex();
	}

size : 528
index : 33
chunk : 1552
chunk : 0x7f3b3114daf0

Reproduction

$> make
$> ./test/run_test.sh 14
$> MallocShowHeap=1 LD_PRELOAD=./libft_malloc.so LD_LIBRARY_PATH=. ./correction 2> f

[bug] segfault on different alignment

#define MALLOC_ALIGNMENT 8

int	main()
{
	malloc(2);
	malloc(2);
}

segfault

[segfault] top value pointing at wrong place resulting in crash

allocated from top (next top = 0x7f3b3f8096b0)
index : 72
result : 0x7f3b3f809318
size : 913

$> make correction FILENAME="test13.c"
$> MallocShowInFile=1 MallocShowHeap=1 LD_PRELOAD=./libft_malloc.so LD_LIBRARY_PATH=. ./correction 12 2> kk

==================++==========================+
 0x7f3b3f8090a0   ||                          | 
------------------++--------------------------+
 0x7f3b3f8090a8   ||      864 (    0x368) |A|P| size
------------------++--------------------------+
 0x7f3b3f8090b0   ||                          | mem
 0x7f3b3f8090b8   || �3�?;�                   | 
                  || (( abbriviated ))        | 
==================++==========================+
 0x7f3b3f809408   ||       0x2a2a2a2a2a2a2a2a | prev_size
------------------++--------------------------+
 0x7f3b3f809410   || 707406368 (0x2a2a2a2a2a2a2a28) |A|-| size
------------------++--------------------------+
 0x7f3b3f809418   || ********                 | mem
 0x7f3b3f809420   || ********                 | 
                  || (( abbriviated ))        | 
==================++==========================+

[fix] large allocation conncetion

large allocation takes really long time

$> time ./test/run_test.sh 3 
run 3
gcc -I includes -I libft -I ft_printf -I . ./test/correction/test3.c -Llibft -lft -Lft_printf -lftprintf libft_malloc_x86_64_Linux.so -o correction

===== test3 Edge-Case Test: Nmalloc =====
Error: mmap failed - size 12530991104
malloc 11230 times, total over 140723017700000 bytes
./test/run_test.sh 3  6.59s user 0.14s system 99% cpu 6.759 total

test3.c version -> a362220

[error] some addresses not recognized

$> ./test/run.sh 10                                                           
[ RUN test no.10 ]
$> gcc -g -I includes -I libft -I ft_printf -I . ./test/single_test/test10.c -L. -lft_malloc -Llibft -lft -Lft_printf -lftprintf -o single_test
$> gcc -I includes -I libft -I ft_printf -I . ./test/single_test/test10.c -Llibft -lft -Lft_printf -lftprintf -o original
> executable 'original' created for compareson

===== test7 Freelists Test: mallocx2 -> free =====
Error: pointer being freed was not allocated
Error: pointer being freed was not allocated
Error: pointer being freed was not allocated
Error: pointer being freed was not allocated
Error: pointer being freed was not allocated

[segfault] wrong chunk size on size 16

void	main()
{
	ft_printf("=== test9 jsut size for space left malloc ===\n");

	void	*ptr1 = malloc(16);
	void	*ptr2 = malloc(16);
	free(ptr1);
	free(ptr2);
}

TINY: 
0x7f0a3bb85000 ~ 0x7f0a3bb9e000 (102400 bytes)
==================++==========================+
 0x7f0a3bb85000   ||                          |
------------------++--------------------------+
 0x7f0a3bb85008   ||     16 (   0x18) | 1 | 0 | size
------------------++--------------------------+
 0x7f0a3bb85010   ||           0x7f0a3bb85030 | fd
------------------++--------------------------+
 0x7f0a3bb85018   ||                     0x18 | bk
==================++==========================+
 0x7f0a3bb85018   ||                     0x18 | prev_size
------------------++--------------------------+
 0x7f0a3bb85020   ||     16 (   0x18) | 0 | 1 | size
------------------++--------------------------+
 0x7f0a3bb85028   ||                          | mem
 0x7f0a3bb85030   ||                          |
==================++==========================+
 0x7f0a3bb85030   ||                          |
------------------++--------------------------+
 0x7f0a3bb85038   || 102320 (0x18fb8) | 1 | 0 | size
------------------++--------------------------+
 0x7f0a3bb85040   ||                      0x0 | fd
------------------++--------------------------+
 0x7f0a3bb85048   ||           0x7f0a3bb85000 | bk
------------------++--------------------------+
 0x7f0a3bb85050   ||                          |
                  || [    102296 (  0x18f98)] |
==================++==========================+
 0x7f0a3bb9dfe8   ||                      0x0 | prev_size
------------------++--------------------------+
 0x7f0a3bb9dff0   ||     -8 (    0x0) | 0 | 1 | size
------------------++--------------------------+
 0x7f0a3bb9dff8   ||                      0x0 | fd
==================++==========================+
Chunk Free
----------------+-------------+----------------+----------------+
 0x7f0a3bb85000 |  26 ( 0x1a) | 0x7f0a3bb85030 |           0x18 | 
----------------+-------------+----------------+----------------+
 0x7f0a3bb85030 | 102330 (0x18fba) |            0x0 | 0x7f0a3bb85000 | 
----------------+-------------+----------------+----------------+

[crush] cruch on print_heap

$> make bonus
$> LD_PRELOAD=./libft_malloc.so MallocDebug=1 MallocShowAbbr=1 gcc  
 0x7f7043cf83a8   ||           0x7f704a583000 | bk
------------------++--------------------------+
 0x7f7043cf83b0   || e/en/LC_                 | 
                  || [    101424 (  0x18c30)] |
==================++==========================+
 0x7f7043d10fe0   ||                  0x18c50 | prev_size
------------------++--------------------------+
 0x7f7043d10fe8   ||       -8 (      0x0) |A|-| size
------------------++--------------------------+
 0x7f7043d10ff0   ||           0x7f704a583000 | fd
==================++==========================+

TINY: 0x7f704a583000 ~ 0x7f704a59d000 (106496 bytes)
==================++==========================+
 0x7f704a583008   ||     1048 (    0x420) |-|P| size
------------------++--------------------------+
                  || (( abbriviated ))        | 
==================++==========================+
 0x7f704a583420   ||                    0x420 | prev_size
------------------++--------------------------+
 0x7f704a583428   ||       88 (     0x60) |A|-| size
------------------++--------------------------+
 0x7f704a583430   ||           0x7f704a583570 | fd
==================++==========================+

TINY: 0x7f704a583570 ~ 0x7f704a59d570 (106496 bytes)
==================++==========================+
 0x7f704a583570   ||       0x54552e53555f6e65 | prev_size
------------------++--------------------------+
 0x7f704a583578   ||  3681592 ( 0x382d40) |A|-| size
------------------++--------------------------+
 0x7f704a583580   ||                          | mem
==================++==========================+
[1]    113306 segmentation fault (core dumped)  LD_PRELOAD=./libft_malloc.so MallocDebug=1 MallocShowAbbr=1 gcc

[segfault] heap infinit loop with wrong chunk size

$> make correction FILENAME="test11.c" 
$> MallocShowAbbr=1 LD_PRELOAD=./libft_malloc.so LD_LIBRARY_PATH=. ./correction 10000 2> f

~~~
<< 1901 >>
free : 0x7feca2c573e8
free : 35
free : 0x7feca38b3780
free : 36
<< 1902 >>
free : 0x7feca2408eb8
free : 35
[1]    63904 segmentation fault (core dumped)  LD_PRELOAD=./libft_malloc.so LD_LIBRARY_PATH=. ./correction 10000

==================++==========================+
�[m 0x7f11fc9f1ab8   ||     1008 (    0x3f8) |A|P| size
�[1;36m------------------++--------------------------+
 0x7f11fc9f1ac0   ||                          | mem
==================++==========================+
�[m 0x7f11fc9f1eb0   ||     1944 (    0x7a0) |A|P| size
�[1;36m------------------++--------------------------+
 0x7f11fc9f1eb8   || ������                   | mem
==================++==========================+
 0x7f11fc9f2648   ||                    0x7a0 | prev_size
------------------++--------------------------+
�[m 0x7f11fc9f2650   ||       -8 (      0x0) |-|-| size
------------------++--------------------------+
 0x7f11fc9f2658   ||                    0x7b0 | fd
------------------++--------------------------+
 0x7f11fc9f2660   ||                    0x3a8 | bk
==================++==========================+
 0x7f11fc9f2648   ||                    0x7a0 | prev_size
------------------++--------------------------+
�[m 0x7f11fc9f2650   ||       -8 (      0x0) |-|-| size
------------------++--------------------------+
 0x7f11fc9f2658   ||                    0x7b0 | fd
------------------++--------------------------+
 0x7f11fc9f2660   ||                    0x3a8 | bk
==================++==========================+
 0x7f11fc9f2648   ||                    0x7a0 | prev_size
------------------++--------------------------+
�[m 0x7f11fc9f2650   ||       -8 (      0x0) |-|-| size
------------------++--------------------------+
 0x7f11fc9f2658   ||                    0x7b0 | fd
------------------++--------------------------+
 0x7f11fc9f2660   ||                    0x3a8 | bk

[fix] alignment of footer

Wrong size block exist

 [5] (80) |-> 0x7fc3b6aa6f50 |-> 0x7fc3b6a91640 |-> 0x7fc3b6ad8f90 |<< 88 >>
-> 0x7fc3b6ad7dc0 |-> 0x7fc3bce1bd40 |-> 0x7fc3bce19290 |
----------+------------------+------------------+------------------+
 [6] (96) |-> 0x7fc3b6a91a50 |-> 0x7fc3b6acd4b0 |-> 0x7fc3bce18210 |-> 0x7fc3bce173c0 |-> 0x7fc3bce13d70 |-> 0x7fc3bce127b0 |-> 0x7fc3bce12640 |
----------+------------------+------------------+------------------+
 [7] (112) |-> 0x7fc3b6a85260 |-> 0x7fc3b6a78670 |-> 0x7fc3b6a93550 |-> 0x7fc3b6aa7c00 |-> 0x7fc3bce1b6d0 |-> 0x7fc3bce17720 |
----------+------------------+------------------+------------------+
 [8] (128) |-> 0x7fc3b6a96820 |-> 0x7fc3b6abce30 |-> 0x7fc3b6ab7900 |-> 0x7fc3b6ac3190 |-> 0x7fc3bce18640 |-> 0x7fc3bce12540 |
----------+------------------+------------------+------------------+
 [9] (144) |-> 0x7fc3b6a7b520 |-> 0x7fc3b6aade50 |-> 0x7fc3b6aad7b0 |-> 0x7fc3b6aabdb0 |-> 0x7fc3bce29d10 |-> 0x7fc3bce13a10 |
----------+------------------+------------------+------------------+
 [10] (160) |-> 0x7fc3b6a5cc90 |-> 0x7fc3b6a9c980 |-> 0x7fc3b6ab8130 |-> 0x7fc3b6ab4660 |-> 0x7fc3b6aac1f0 |-> 0x7fc3bce1fb00 |
----------+------------------+------------------+------------------+
 [11] (176) |-> 0x7fc3b6a5e240 |-> 0x7fc3b6a77a10 |-> 0x7fc3b6a9ff30 |-> 0x7fc3b6a98260 |-> 0x7fc3b6abeb60 |-> 0x7fc3b6ad8110 |-> 0x7fc3bce16ad0 |
----------+------------------+------------------+------------------+
 [12] (192) |-> 0x7fc3b6a7d370 |-> 0x7fc3bce27f30 |-> 0x7fc3bce27380 |
----------+------------------+------------------+------------------+
 [13] (208) |-> 0x7fc3b6a89e70 |-> 0x7fc3b6a88440 |-> 0x7fc3b6a76ff0 |-> 0x7fc3b6ab5320 |-> 0x7fc3b6ad34d0 |-> 0x7fc3bce2af10 |<< 216 >>
-> 0x7fc3bce29890 |-> 0x7fc3bce12d30 |

Those are the blocks right before footer blocks

==================++==========================+
 0x7fc3b6ad8f90   ||                          | 
------------------++--------------------------+
�[m 0x7fc3b6ad8f98   ||       80 (     0x58) |-|P| size
------------------++--------------------------+
 0x7fc3b6ad8fa0   ||           0x7fc3b6ad7dc0 | fd
------------------++--------------------------+
 0x7fc3b6ad8fa8   ||           0x7fc3b6a91640 | bk
------------------++--------------------------+
 0x7fc3b6ad8fb0   ||                          | 
                  || [        56 (     0x38)] |
==================++==========================+
�[2m 0x7fc3b6ad8fe8   ||                     0x58 | prev_size
------------------++--------------------------+
�[m�[2m 0x7fc3b6ad8ff0   ||       -8 (      0x0) |A|-| size
------------------++--------------------------+
 0x7fc3b6ad8ff8   ||           0x7fc3bce12000 | fd
==================++==========================+

fix footer size

[crush] with malloc call

$> LD_PRELOAD=./libft_malloc.so MallocShowAbbr=1 git
[malloc] by (null)	: malloc(28) = 0x7fbedfaf2060
[malloc] by (null)	: malloc(5) = 0x7fbedfaf2090
[free] by (null)	: free(0x7fbedfaf2090)
[malloc] by (null)	: malloc(120) = 0x7fbedfaf2090
[malloc] by __strdup	: malloc(12) = 0x7fbedfaf2110
[malloc] by (null)	: malloc(776) = 0x7fbedfaf2130
[malloc] by (null)	: malloc(112) = 0x7fbedfaf2440
[malloc] by (null)	: malloc(1336) = 0x7fbed97b9010
[malloc] by (null)	: malloc(216) = 0x7fbedfaf24c0
[malloc] by (null)	: malloc(432) = 0x7fbedfaf25a0
[malloc] by (null)	: malloc(104) = 0x7fbedfaf2760
[malloc] by (null)	: malloc(88) = 0x7fbedfaf27d0
[malloc] by (null)	: malloc(120) = 0x7fbedfaf2830
[malloc] by (null)	: malloc(168) = 0x7fbedfaf28b0
[malloc] by (null)	: malloc(104) = 0x7fbedfaf2960
[malloc] by (null)	: malloc(80) = 0x7fbedfaf29d0
[malloc] by (null)	: malloc(192) = 0x7fbedfaf2a30
[malloc] by __strdup	: malloc(12) = 0x7fbedfaf2b00
[malloc] by (null)	: malloc(171) = 0x7fbedfaf2b20
[malloc] by __strdup	: malloc(12) = 0x7fbedfaf2be0
[malloc] by (null)	: malloc(181) = 0x7fbedfaf2c00
[free] by setlocale	: free(0x7fbedfaf2b20)
[malloc] by __strdup	: malloc(12) = 0x7fbedfaf2cc0
[malloc] by (null)	: malloc(191) = 0x7fbedfaf2ce0
[free] by setlocale	: free(0x7fbedfaf2c00)
[malloc] by __strdup	: malloc(6) = 0x7fbedfaf2db0
[malloc] by __strdup	: malloc(4) = 0x7fbedfaf2dd0
[free] by (null)	: free(0x7fbedfaf2010)
[malloc] by (null)	: malloc(224) = 0x7fbedfaf2df0
[malloc] by (null)	: malloc(112) = 0x7fbedfaf2ee0
[malloc] by (null)	: malloc(24) = 0x7fbedfaf2f60
[malloc] by __strdup	: malloc(15) = 0x7fbedfaf2f80
[free] by (null)	: free(0x7fbedfaf2f80)
[free] by (null)	: free(0x7fbedfaf2010)
[free] by (null)	: free(0x7fbedfaf2fa0)
[malloc] by (null)	: malloc(49) = 0x7fbedfaf2f80
[free] by (null)	: free(0x7fbedfaf2f80)
[malloc] by fopen	: malloc(472) = 0x7fbedfaf2f80
[malloc] by _IO_file_doallocate	: malloc(4096) = 0x7fbed97b9610
[free] by _IO_setb	: free(0x7fbed97b9610)
[free] by _IO_fclose	: free(0x7fbedfaf2f80)
[malloc] by (null)	: malloc(5)[1]    18099 segmentation fault (core dumped)  LD_PRELOAD=./libft_malloc.so MallocShowAbbr=1 git

[impl] freelist bitmap

[bug] inf. loop in show heap

$> MallocShowHeap=1 ./test_malloc


 0x7f515198cfe8   ||                      0x0 | prev_size
------------------++--------------------------+
 0x7f515198cff0   ||     -8 (    0x0) | 0 | 0 | size
------------------++--------------------------+
 0x7f515198cff8   ||                      0x0 | fd
------------------++--------------------------+
 0x7f515198d000   ||                      0x0 | bk
------------------++--------------------------+
 0x7f515198d008   ||                          |
                  || [       -32 (0xffffffffffffffe0)] |
==================++==========================+
 0x7f515198cfe8   ||                      0x0 | prev_size
------------------++--------------------------+
 0x7f515198cff0   ||     -8 (    0x0) | 0 | 0 | size
------------------++--------------------------+
 0x7f515198cff8   ||                      0x0 | fd
------------------++--------------------------+
 0x7f515198d000   ||                      0x0 | bk
------------------++--------------------------+
 0x7f515198d008   ||                          |
                  || [       -32 (0xffffffffffffffe0)] |
==================++==========================+
 0x7f515198cfe8   ||                      0x0 | prev_size
------------------++--------------------------+
 0x7f515198cff0   ||     -8 (    0x0) | 0 | 0 | size
------------------++--------------------------+
 0x7f515198cff8   ||                      0x0 | fd
------------------++--------------------------+
 0x7f515198d000   ||                      0x0 | bk
------------------++--------------------------+
 0x7f515198d008   ||                          |
                  || [       -32 (0xffffffffffffffe0)] |
==================++==========================+
 0x7f515198cfe8   ||                      0x0 | prev_size
------------------++--------------------------+
 0x7f515198cff0   ||     -8 (    0x0) | 0 | 0 | size
------------------++--------------------------+
 0x7f515198cff8   ||                      0x0 | fd
------------------++--------------------------+
 0x7f515198d000   ||                      0x0 | bk
------------------++--------------------------+
 0x7f515198d008   ||                          |
                  || [       -32 (0xffffffffffffffe0)] |
==================++==========================+
 0x7f515198cfe8   ||                      0x0 | prev_size
------------------++--------------------------+
 0x7f515198cff0   ||     -8 (    0x0) | 0 | 0 | size
------------------++--------------------------+
 0x7f515198cff8   ||                      0x0 | fd

[bug] is_alloced check failed

$> ./test/benchmark.sh
$> LD_PRELOAD=./libft_malloc.so LD_LIBRARY_PATH=. ./single_test 100

===== Benchmark-tiny: time overhead =====
100 loops of 1000 mallocs and 500 free
-> 100000 mallocs, 50000 frees
Error: pointer being freed was not allocated
Error: pointer being freed was not allocated
Error: pointer being freed was not allocated
Error: pointer being freed was not allocated
Error: pointer being freed was not allocated
Error: pointer being freed was not allocated
Error: pointer being freed was not allocated
Error: pointer being freed was not allocated

[segfault] fish

fish crush sometimes

[error] realloc on size change is no longer recognized

$> MallocDebug=1 LD_PRELOAD=./libft_malloc.so bash    
[ malloc] by xmalloc      : malloc(16) = 0x7f552f3be170
[ malloc] by xmalloc      : malloc(16) = 0x7f552f3be190
[ malloc] by xmalloc      : malloc(16) = 0x7f552f3be1b0
[ malloc] by xmalloc      : malloc(16) = 0x7f552f3be1d0
[ malloc] by xmalloc      : malloc(16) = 0x7f552f3be1f0
[ malloc] by xmalloc      : malloc(16) = 0x7f552f3be210
[realloc] by xrealloc     : realloc(0x7f552f3aeb90, 1536)address: 0x7f552f3aeb80
magazine->type: 1
Error: pointer being realloc'd was not allocated
 -> terminated
[ malloc]                 : malloc(50) = 0x7f552f3be230
[   free]                 : free(0x7f552f3be230) -> terminated
[ malloc] by fopen        : malloc(472) = 0x7f552f3ad6e0
[ malloc] by _IO_file_doallocate : malloc(4096) = 0x7f5529089410
[realloc]                 : realloc(0x0, 1600) = 0x7f552908a610
[realloc]                 : realloc(0x0, 1024) = 0x7f552f3b57f0
[realloc]                 : realloc(0x7f552f3b57f0, 2048)address: 0x7f552f3b57e0
magazine->type: 1
Error: pointer being realloc'd was not allocated
 -> terminated
[   free] by _IO_setb     : free(0x7f5529089410) -> terminated
[   free] by fclose       : free(0x7f552f3ad6e0) -> terminated
[ malloc]                 : malloc(5) = 0x7f552f3be270
[ malloc]                 : malloc(55) = 0x7f552f3be230
[ malloc]                 : malloc(168) = 0x7f552f3ae2c0

[crush] segfault on small size

malloc(1) causes segfault
1 ~ 8

[impl] double free

[impl] `show_alloc_mem` check overflow

#include "malloc_internal.h"
#include "ft_printf.h"

static size_t	sum_overflow_check(size_t dst, size_t add, bool *overflow)
{
	if (*overflow)
		return (dst);
	if (dst + add >= dst)
		return (dst + add);
	*overflow = true;
	return (dst);
}

static size_t	_print_large_simple(t_mmap_chunk *lst, bool *overflow)
{
	size_t	sum;

	sum = 0;
	while (lst)
	{
		ft_printf("LARGE : %p\n", lst);
		ft_printf("%p ~ %p : %zu bytes\n", MEM(lst), MEM(lst) + CHUNKSIZE(lst), CHUNKSIZE(lst));
		sum = sum_overflow_check(sum, CHUNKSIZE(lst), overflow);
		lst = lst->fd;
	}
	return (sum);
}

static size_t	_print_malloc_simple(char *zone, t_magazine magazine, bool *overflow)
{
	t_malloc_chunk	*chunk;
	size_t			sum;
	size_t			size;

	sum = 0;
	chunk = magazine.regions;
	ft_printf("%s : %p\n", zone, chunk);
	while (!IS_FOOTER(chunk))
	{
		if (IS_ALLOCED(chunk))
		{
			size = ALLOCSIZE(chunk);
			ft_printf("%p ~ %p : %zu bytes\n", MEM(chunk), MEM(chunk) + size, size);
			sum = sum_overflow_check(sum, size, overflow);
		}
		chunk = NEXTCHUNK(chunk);
	}
	return (sum);
}

void	show_alloc_mem()
{
	size_t	total;
	size_t	sum;
	bool	overflow;

	total = 0;
	overflow = false;
	sum = _print_malloc_simple("TINY", g_malloc.tiny_magazine, &overflow);
	total = sum_overflow_check(total, sum, &overflow);
	sum = _print_malloc_simple("SMALL", g_malloc.small_magazine, &overflow);
	total = sum_overflow_check(total, sum, &overflow);
	sum = _print_large_simple(g_malloc.large_allocations, &overflow);
	total = sum_overflow_check(total, sum, &overflow);
	if (overflow)
		ft_printf("TOTAL : over %zu bytes\n", SIZE_MAX);
	else
		ft_printf("TOTAL : %zu bytes\n", total);
}

[bug] inf loop in freelist

$>  make correction FILENAME="test14.c"
$> MallocShowInFile=1 MallocShowHeap=1 LD_PRELOAD=./libft_malloc.so LD_LIBRARY_PATH=. ./correction 12 2> file

----------+------------------+------------------+------------------+
 [9] (72) |-> 0x7feea467d348 |<< 776 >>

----------+------------------+------------------+------------------+
 [10] (80) |
----------+------------------+------------------+------------------+
 [11] (88) |-> 0x7feea46ca258 |-> 0x7feea46ca258 |-> 0x7feea46ca258 |-> 0x7feea46ca258 |-> 0x7feea46ca258 |-> 0x7feea46ca258 |-> 0x7feea46ca258 |-> 0x7feea46ca258 |-> 0x7feea46ca258 |-> 0x7feea46ca258 |-> 0x7feea46ca258 |-> 0x7feea46ca258 |-> 0x7feea46ca258 |-> 0x7feea46ca258 |-> 0x7feea46ca258 |-> 0x7feea46ca258 |-> 0x7feea46ca258

[fix] realloc over different size zone

alloced tiny and realloc to small
alloced small and realloc to large

    /*
     * If the new size suits the tiny allocator and the pointer being resized
     * belongs to a tiny region, try to reallocate in-place.
     */
    if ((new_size + TINY_QUANTUM - 1) <= (NUM_TINY_SLOTS - 1) * TINY_QUANTUM) {
	if (tiny_region_for_ptr_no_lock(szone, ptr) != NULL) {
	    if (tiny_try_realloc_in_place(szone, ptr, old_size, new_size)) {
		return ptr;
	    }
	}