C | analysis of malloc implementation

brk（sbrk） and mmap function

　　 First ,linux The system provides the user with the requested memory brk(sbrk) and mmap function . Let's take a look at these functions first .

brk() and sbrk()

The role of both is to expand heap The upper bound of brk
Brk（） Parameter set to new brk Upper bound address , Successfully returns 1, Failure to return 0;
Sbrk（） The parameter of is the size of the requested memory , return heap The new upper bound brk The address of

mmap()

#include <sys/mman.h>
void *mmap(void *addr, size\_t length, int prot, int flags, int fd, off\_t offset);
int munmap(void *addr, size_t length);

Mmap The first use of is to map this disk file to memory ; The second use is anonymous mapping , Do not map disk files , And request a piece of memory from the mapping area .
Malloc It uses mmap The second use of （ Anonymous mapping ）.
Munmap Function is used to free memory .

Malloc Realization principle ：

　　 because brk、sbrk、mmap All belong to system call , If each request for memory , Call these three , Then every time a system call is generated , Affect performance ; secondly , In this way, the applied memory is prone to fragmentation , Because the heap goes from low address to high address , If the high address memory is not released , Low address memory cannot be recycled .
　　
　　 therefore malloc It adopts the management mode of memory pool （ptmalloc）,Ptmalloc The memory is divided into many blocks by boundary marking , So as to manage the allocation and recycling of memory . For memory allocation function malloc The efficiency of ,ptmalloc Will request a piece of memory from the operating system in advance for users to use , When we apply for and release memory ,ptmalloc Will manage these memories , And through some strategies to determine whether to recycle it to the operating system . The biggest advantage of this is , Make it more efficient for users to apply for and release memory , Avoid excessive memory fragmentation .

chunk The basic organizational unit of a memory block

stay ptmalloc The structure is defined in the implementation source code of malloc_chunk To describe these blocks .malloc_chunk The definition is as follows ：

1.struct malloc_chunk {  
2.  INTERNAL_SIZE_T      prev_size;    /* Size of previous chunk (if free).  */  
3.  INTERNAL_SIZE_T      size;         /* Size in bytes, including overhead. */  
4.  
5.  struct malloc_chunk* fd;           /* double links -- used only if free. */  
6.  struct malloc_chunk* bk;  
7.  
8.  /* Only used for large blocks: pointer to next larger size.  */  
9.  struct malloc_chunk* fd_nextsize;      /* double links -- used only if free. */  
10.  struct malloc_chunk* bk_nextsize; 
11.};  

chunk The definition of is quite simple , Give a brief introduction to each domain :
　　prev_size: If the previous one chunk Is free , This field represents the previous chunk Size , If the previous one chunk Not idle , This field is meaningless .
　　size ： At present chunk Size , And recorded the current chunk And the previous one chunk Some properties of , Including the previous one chunk Is it in use , At present chunk Is it through mmap Acquired memory , At present chunk Whether it belongs to a non primary distribution area .
　　 fd and bk ： The pointer fd and bk Only when it's time to chunk Blocks exist only when they are idle , Its function is to transfer the corresponding idle data chunk Blocks are added to the free chunk Unified management in block list , If it's time to chunk Blocks are assigned to the application to use , Then these two pointers are useless （ The chunk The block has been removed from the free chain ） 了 , So it's also used as a space for applications , Instead of wasting .
　　fd_nextsize and bk_nextsize: When the current chunk Exist in large bins In the middle of the day , large bins Free in chunk Is sorted by size , But the same size chunk There may be more than one , Adding these two fields can speed up the traversal process chunk , And find the leisure that meets your needs chunk , fd_nextsize Point to the next one than the current chunk The first big one is free chunk , bk_nextszie Point to the previous one than the present chunk The first one that's small is free chunk . If it's time to chunk Blocks are assigned to the application to use , Then these two pointers are useless （ The chunk Block has been removed from size Remove from the chain ） 了 , So it's also used as a space for applications , Instead of wasting .

Free list bins

　　 When users use free Function to free up memory ,ptmalloc It will not be returned to the operating system immediately , But be ptmalloc Its own free linked list bins It's under management , So when the next process needs malloc When a piece of memory ,ptmalloc From the idle bins Find a memory block of appropriate size to allocate to the user . This benefit avoids frequent system calls , Reduce memory allocation overhead .
　　malloc Will be similar in size chunk Link up with a double linked list , Such a linked list is called a bin.ptmalloc A total of 128bin. Every bins Both maintain two-way linked lists of similar sizes chunk. be based on chunk Size , There are several available bins：
　　1、Fast bin
　　2、Unsorted bin
　　3、Small bin
　　4、Large bin
　　
　　 Save these bin The data structure of is ：
　　fastbinsY： This array is used to hold fast bins.
　　bins： This array is used to hold unsorted、small as well as large bins, A total of... Can be accommodated 126 individual ：

　　 When the user calls malloc When , You can quickly find out whether the memory size that users need to allocate is being maintained bin On , If I were in one of these bin On , You can use the two-way linked list to find the appropriate chunk Memory block for user use .

#include <unistd.h>
int brk( const void *addr )
void* sbrk ( intptr_t incr );

Memory allocation malloc technological process

1. Get the lock of the allocation area , Prevent multithreading conflicts .
2. Calculate the actual amount of memory that needs to be allocated chunk Actual size .
3. Judge chunk Size , If it is less than max_fast（64Ｂ）, Then try to fast bins Pick the right one chunk, If so, the allocation ends . otherwise , next step ;
4. Judge chunk Whether the size is less than 512B, If it is , From small bins Go up and find out chunk, If there is a suitable , The assignment ends . Otherwise, the next step ;
5. ptmalloc First of all, I will traverse fast bins Medium chunk, Will be adjacent to chunk A merger , And link to unsorted bin And then traverse unsorted bins. If unsorted bins There is only one chunk And greater than the amount to be allocated chunk, Then cut , And the rest chunk Keep throwing back unsorted bins; If unsorted bins There are sizes and assignments on the chunk equal , Then return to , And from unsorted bins Delete ; If unsorted bins In a chunk size Belong to small bins The scope of the , Put in small bins The head of ; If unsorted bins In a chunk size Belong to large bins The scope of the , Find the right place to put . If the allocation is not successful , Go to the next step ;
6. from large bins Find the right chunk after , And then cut , Some are assigned to users , Put the rest in unsorted bin in .
7. If searching fast bins and bins I didn't find the right one chunk, Then we need to operate top chunk To allocate
   When top chunk When the size is larger than the size requested by the user ,top chunk It will be divided into two parts ：User chunk（ User request size ） and Remainder chunk（ Remaining size ）. among Remainder chunk Become the new top chunk.
   　　 When top chunk When the size is less than the size requested by the user ,top chunk Just through sbrk（main arena） or mmap（thread arena） System calls are used to expand the capacity of .
8. Here we are , explain top chunk Nor can it meet the distribution requirements , therefore , So there are two options : Such as The result is the main distribution area , call sbrk(), increase top chunk size ; If it is a non primary distribution area , call mmap To assign a new sub-heap, increase top chunk size ; Or use mmap() To directly allocate . stay here , Need to rely on chunk To determine which method to use . Determine the required allocation chunk Whether the size is greater than or equal to mmap Assignment threshold , If so , Then go to the next step , call mmap Distribute , Or jump to the 10 Step , increase top chunk Size .
9. Use mmap The system call maps a block of memory space for the program chunk_size align 4kB Size space . Then return the memory pointer to the user .
10. Determine whether it is the first call malloc, If it is the main distribution area , You need to perform an initialization , Distribute One piece is... In size (chunk_size + 128KB) align 4KB The size of the space as the initial heap. If you have already It has been transformed , The main allocation area calls sbrk() increase heap Space , The sub main distribution area is top chunk Mid cut Cut out one chunk, Make it meet the distribution needs , And return the memory pointer to the user

Memory recycling process

1. Get the lock of the allocation area , Ensure thread safety .
2. If free Is a null pointer , Then return to , Don't do anything? .
3. Judge the present chunk Whether it is mmap Mapped area mapped memory , If it is , directly munmap() Free up this memory . The previous has been used chunk In the data structure of , We can see that there is M To identify whether it is mmap Mapped memory .
4. Judge chunk Whether or not top chunk adjacent , If it's adjacent , Directly with top chunk Merge （ and top chunk Adjacency is equivalent to adjacency to free memory block in allocation area ）. Go to step 8
5. If chunk Is larger than max_fast（64b）, Put in unsorted bin, And check if there is a merge , There is a merger with top chunk adjacent , Then go to step 8; If there is no merger, then free.
6. If chunk The size of is less than max_fast（64b）, Put it directly in fast bin,fast bin It hasn't changed chunk The state of . No consolidation , be free; There is a merger , Go to step 7
7. stay fast bin, If at present chunk Next chunk It's also free , Then these two chunk Merge , Put in unsorted bin above . If the combined size is greater than 64B, Will trigger the fast bins Merge operation of ,fast bins Medium chunk Will be traversed , And with the adjacent free chunk A merger , After the merger chunk Will be put in unsorted bin in ,fast bin It's going to be empty . After the merger chunk and topchunk adjacent , Will be merged into topchunk in . Go to step 8
8. Judge top chunk Is the size of greater than mmap Contraction threshold （ The default is 128KB）, If so , For the main distribution area , Will try to return top chunk Part of the is given to the operating system .free end .

  from malloc The underlying implementation of （ptmalloc）_ Programming essays and essays -CSDN Blog _ptmalloc