Anyone who has used or learned C is no stranger to malloc. Everyone knows that malloc can allocate a contiguous memory space and can be freed by free when it is no longer used. However, many programmers are not familiar with the things behind malloc, and many even use malloc as a system call or C keyword provided by the operating system. In fact, malloc is just a normal function provided in C's standard library, and the basic idea of ​​implementing malloc is not complicated. Any programmer who knows a little about C and the operating system can easily understand it.
This article describes the mechanism behind malloc by implementing a simple malloc. Of course, compared to the existing C standard library implementation (such as glibc), the malloc we implemented is not particularly efficient, but this implementation is much simpler than the current real malloc implementation, so it is easy to understand. What is important is that this implementation is true in principle with the real implementation.
This article will first introduce some of the basic knowledge required, such as the operating system's memory management of the process and related system calls, and then gradually implement a simple malloc. For the sake of simplicity, this article will only consider the x86_64 architecture, the operating system is Linux.
1 What is malloc
2 preliminary knowledge
2.2.1 Memory Arrangement
2.2.2 Heap Memory Model
2.2.3 brk and sbrk
2.2.4 Resource Limit and rlimit
2.1.1 Virtual Memory Address and Physical Memory Address
2.1.2 Page and address composition
2.1.3 Memory Pages and Disk Pages
2.1 Linux Memory Management
2.2 Linux process level memory management
3 implement malloc
3.2.1 Data Structure
3.2.2 Finding the right block
3.2.3 Opening up new blocks
3.2.4 split block
3.2.5 malloc implementation
3.2.6 implementation of calloc
3.2.7 free implementation
3.2.8 Realloc implementation
3.1 Toy realization
3.2 Formal implementation
3.3 Legacy issues and optimization
4 Other references
1 What is malloc
Before implementing malloc, we must make a definition of malloc relatively officially.
According to the definition of the standard C library function, malloc has the following prototype:
Void* malloc(size_t size);
The function to be implemented by this function is to allocate a contiguous amount of available memory in the system, which has the following requirements:
The memory size allocated by malloc is at least the number of bytes specified by the size parameter.
The return value of malloc is a pointer to the starting address of a piece of available memory.
The address allocated by calling malloc multiple times cannot overlap, unless the address allocated by malloc is released.
Malloc should complete memory allocation and return as soon as possible (cannot use NP-hard's memory allocation algorithm)
When implementing malloc, you should implement both memory size adjustment and memory release functions (ie realloc and free).
More instructions for malloc can be found by typing the following command on the command line:
Man malloc
2 preliminary knowledge
Before implementing malloc, you need to explain some of the Linux system memory related knowledge.
2.1 Linux Memory Management
2.1.1 Virtual Memory Address and Physical Memory Address
For simplicity, modern operating systems generally employ virtual memory address technology when dealing with memory addresses. That is, at the assembler (or machine language) level, when a memory address is involved, the virtual memory address is used. When using this technology, each process seems to enjoy a 2N
Byte of memory, where N is the number of bits in the machine. For example, under 64-bit CPU and 64-bit operating system, the virtual address space of each process is 264.
Byte.
The role of this virtual address space is mainly to simplify the writing of the program and to facilitate the isolation management of the inter-process memory by the operating system. The real process is unlikely (and is not used). Such a large memory space can actually be used. Depends on the size of the physical memory.
Since the virtual address is adopted at the machine language level, when the actual machine code program involves a memory operation, the virtual address needs to be converted into a physical memory address according to the actual context in which the current process runs, so that the operation of the real memory data can be realized. This conversion is typically done by a hardware called MMU (Memory Management Unit).
2.1.2 Page and address composition
In modern operating systems, neither virtual memory nor physical memory is managed in bytes, but in pages. A memory page is a general term for a fixed-size contiguous memory address. For Linux, a typical memory page size is 4096 bytes (4K).
So the memory address can be divided into page number and page offset. The following takes a 64-bit machine, 4G physical memory, and 4K page size as an example. The composition of the virtual memory address and the physical memory address is as follows:
Above is the virtual memory address, below is the physical memory address. Since the page size is 4K, the cheaper page is represented by the lower 12 bits, and the remaining high addresses represent the page number.
The MMU mapping unit is not a byte, but a page. This mapping is implemented by looking up a data structure page table of resident memory. Now computer-specific memory address mapping is more complicated, in order to speed up will introduce a series of cache and optimization, such as TLB and other mechanisms. A simplified translation of the memory address is given below. Although simplified, the basic principles are consistent with the real situation of modern computers.
2.1.3 Memory Pages and Disk Pages
We know that memory is generally regarded as a cache of disks. Sometimes, when the MMU is working, it will find that the page table indicates that a memory page is not in physical memory. At this time, a page fault will be triggered, and the system will The corresponding place on the disk loads the disk page into memory and then re-executes the machine instructions that failed due to page faults. About this part, because it can be seen as transparent to the malloc implementation, so it will not be described in detail. If you are interested, you can refer to the relevant chapters of "In-depth understanding of computer systems".
Finally, attach a process that is more in line with the real address translation found on Wikipedia for your reference. This picture adds the process of TLB and page fault exception (image source page).
2.2 Linux process level memory management
2.2.1 Memory Arrangement
Understand the relationship between virtual memory and physical memory and related mapping mechanisms. Let's look at how memory is arranged in a process.
Take the Linux 64-bit system as an example. In theory, the 64bit memory address free space is 0x0000000000000000 ~ 0xFFFFFFFFFFFFFFFF, which is a very large space, Linux actually uses only a small part (256T).
According to the Linux kernel related documentation, the Linux 64-bit operating system uses only the lower 47 bits and the upper 17 bits for expansion (only all 0s or all 1s). Therefore, the actual address used is space 0x0000000000000000 ~ 0x00007FFFFFFFFFFF and 0xFFFF800000000000 ~ 0xFFFFFFFFFFFFFFFF, where the user space (User Space) and the kernel space (Kernel Space). The illustration is as follows:
For users, the main focus is User Space. After zooming in on the User Space, you can see that it is divided into the following sections:
Code: This is the lowest address part of the entire user space, which stores the instructions (that is, the executable machine code compiled by the program)
Data: This is the initialized global variable.
BSS: This is the uninitialized global variable.
Heap: Heap, this is the focus of our article. The heap grows from low address to high address. The brk related system call mentioned later is to allocate memory from here.
Mapping Area: This is the area associated with the mmap system call. Most actual malloc implementations will consider allocating a larger block of memory through mmap, which is not discussed in this article. This area grows from high address to low address
Stack: This is the stack area, growing from high address to low address
Below we mainly focus on the operation of the Heap area. Students who are interested in the entire Linux memory arrangement can refer to other materials.
2.2.2 Heap Memory Model
In general, the memory requested by malloc is mainly allocated from the Heap area (this article does not consider the case of applying large chunks of memory through mmap).
It is known from the above that the virtual memory address space faced by the process can only be used if it is mapped to the physical memory address by page. Due to physical storage capacity limitations, it is not possible to map the entire heap virtual memory space to actual physical memory. Linux management of the heap is as follows:
Linux maintains a break pointer that points to an address in the heap space. The address space from the heap start address to the break is mapped and can be accessed by the process. From the break up, it is an unmapped address space. If the space is accessed, the program will report an error.
2.2.3 brk and sbrk
It is known from the above that to increase the actual available heap size of a process, it is necessary to move the break pointer to a high address. Linux calls the break pointer through the brk and sbrk system calls. The prototypes of the two system calls are as follows:
Int brk(void*addr);
Void*sbrk(intptr_t increment);
Brk sets the break pointer directly to an address, and sbrk moves the break from the current position by the increment specified by increment. Brk returns 0 when the execution succeeds, otherwise it returns -1 and sets errno to ENOMEM; when sbrk succeeds, it returns the address pointed to before the break move, otherwise it returns (void *)-1.
One trick is that if you set increment to 0, you get the address of the current break.
Also note that since Linux is memory mapped by page, if break is set to not align by page size, the system will actually map a complete page at the end, thus actually mapping the memory space than break Point to a bigger place. But using the address after the break is dangerous (although there may be a small block of available memory after the break).
2.2.4 Resource Limit and rlimit
The resources allocated by the system to each process are not unlimited, including the mapable memory space, so each process has an rlimit indicating the upper limit of the resources available to the current process. This limit can be obtained by the getrlimit system call. The following code gets the rlimit of the current process virtual memory space:
Int main(){
Struct rlimit *limit =(struct rlimit *)malloc(sizeof(struct rlimit));
Getrlimit(RLIMIT_AS, limit);
Printf("soft limit: %ld, hard limit: %ld", limit->rlim_cur, limit->rlim_max);
}
Where rlimit is a structure:
Struct rlimit {
Rlim_t rlim_cur;/* Soft limit */
Rlim_t rlim_max;/* Hard limit (ceiling for rlim_cur) */
};
Each resource has soft and hard limits, and rlimit can be conditionally set by setrlimit. The hard limit is the upper limit of the soft limit. The non-privileged process can only set the soft limit and cannot exceed the hard limit.
3 implement malloc
3.1 Toy realization
Before we begin to discuss the implementation of malloc, we can use the above knowledge to implement a simple but almost impossible to use real toy malloc, right to review the above knowledge:
/* A toy malloc */
#include
#include
Void*malloc(size_t size)
{
Void*p;
p = sbrk(0);
If(sbrk(size)==(void*)-1)
Return NULL;
Return p;
}
This malloc increments the number of bytes specified by size on the basis of the current break and returns the address of the previous break. This malloc cannot be used in real scenes because it lacks a record of the allocated memory and is not convenient for memory release.
3.2 Formal implementation
The following is a serious discussion of the implementation of malloc.
3.2.1 Data Structure
First we need to determine the data structure used. A simple and feasible solution is to organize the heap memory space in the form of blocks. Each block is composed of a meta area and a data area. The meta area records the meta information of the data block (data area size, idle flag, pointer, etc. The data area is the real allocated memory area, and the first byte address of the data area is the address returned by malloc.
You can define a block with the following structure:
Typedefstruct s_block *t_block;
Struct s_block {
Size_t size;/* data area size*/
T_block next;/* Pointer to the next block */
Int free; /* Is it a free block */
Int padding; / * padding 4 bytes, guarantee the length of the meta block is a multiple of 8 * /
Char data[1]/* This is a virtual field indicating the first byte of the data block. The length should not be counted in meta */
};
Since we only consider 64-bit machines, for convenience, we fill an int at the end of the structure, so that the length of the structure itself is a multiple of 8, in order to align the memory. The schematic is as follows:
3.2.2 Finding the right block
Now consider how to find the right block in the block chain. There are generally two search algorithms:
First fit: From the beginning, use the block whose first data area size is larger than the required size.
Best fit: From the beginning, iterate through all the blocks, using the block with the data area size larger than size and the smallest difference as the allocated block.
Both methods have their own advantages, best fit has a higher memory usage (higher payload), and first fit has better operating efficiency. Here we use the first fit algorithm.
/* First fit */
T_block find_block(t_block *last,size_t size){
T_block b = first_block;
While(b &&!(b->free && b->size >= size)){
*last = b;
b = b->next;
}
Return b;
}
Find_block starts with frist_block, finds the first block that meets the requirements and returns the block start address. If it is not found, it returns NULL. Here, when traversing, a pointer called last is updated. This pointer always points to the block that is currently traversed. This is to open up new blocks if you can't find a suitable block, as you will see in the next section.
3.2.3 Opening up new blocks
If the existing block can not meet the size requirements, you need to open a new block at the end of the list. The key here is how to create a struct using only sbrk:
#define BLOCK_SIZE 24/* Since there is a virtual data field, sizeof cannot calculate the length of the meta. This is manually set */
T_block extend_heap(t_block last,size_t s){
T_block b;
b = sbrk(0);
If(sbrk(BLOCK_SIZE + s)==(void*)-1)
Return NULL;
B->size = s;
B->next = NULL;
If(last)
Last->next = b;
B->free =0;
Return b;
}
3.2.4 split block
First fit has a fatal flaw, which may cause a small size to occupy a large block. In this case, in order to improve the payload, it should be split into a new block if the remaining data area is large enough. , as shown below:
Implementation code:
Void split_block(t_block b,size_t s){
T_block new;
New= b->data + s;
New->size = b->size - s - BLOCK_SIZE ;
New->next = b->next;
New->free =1;
B->size = s;
B->next =new;
}
3.2.5 malloc implementation
With the above code, we can use them to integrate into a simple but initially available malloc. Note that we first need to define the header first_block of the block list, initialized to NULL; in addition, we need the remaining space at least BLOCK_SIZE + 8 to perform the split operation.
Since we want the data area allocated by malloc to be aligned in 8 bytes, we need to adjust the size to a multiple of 8 which is greater than size when the size is not a multiple of 8.
Size_t align8(size_t s){
If(s &0x7==0)
Return s;
Return((s >>3)+1)<<3;
}
#define BLOCK_SIZE 24
Void*first_block=NULL;
/* other functions... */
Void*malloc(size_t size){
T_block b, last;
Size_t s;
/* Align address*/
s = align8(size);
If(first_block){
/* Find the appropriate block */
Last = first_block;
b = find_block(&last, s);
If(b){
/* If possible, split */
If((b->size - s)>=( BLOCK_SIZE +8))
Split_block(b, s);
B->free =0;
}else{
/* There is no suitable block to open a new */
b = extend_heap(last, s);
If(!b)
Return NULL;
}
}else{
b = extend_heap(NULL, s);
If(!b)
Return NULL;
First_block = b;
}
Return b->data;
}
3.2.6 implementation of calloc
With malloc, implementing calloc takes only two steps:
Malloc a piece of memory
Set the contents of the data area to 0
Since our data area is aligned in 8 bytes, in order to improve efficiency, we can set 0 for every 8 bytes instead of one byte. We can do this by creating a size_t pointer and forcing the memory area to be treated as a size_t type.
Void*calloc(size_t number,size_t size){
Size_t*new;
Size_t s8, i;
New= malloc(number * size);
If(new){
S8 = align8(number * size)>>3;
For(i =0; i < s8; i++)
New[i]=0;
}
Returnnew;
}
3.2.7 free implementation
The implementation of free is not as simple as it seems, here we have to solve two key issues:
How to verify that the incoming address is a valid address, that is, the first address of the data area that is actually allocated by malloc
How to solve the fragmentation problem
First of all, we must ensure that the address of the incoming free is valid. This effectively includes two aspects:
The address should be in the area allocated by malloc, ie within the range of first_block and current break pointer
This address is indeed allocated by our own malloc.
The first problem is better solved, as long as the address comparison is sufficient, the key is the second problem. There are two solutions here: one is to embed a magic number field in the structure body. Before the free, check whether the value of the specific position is the magic number set by us by relative offset. Another method is to add a magic pointer to the structure body. This pointer points to the first byte of the data area (that is, the address passed in when the law is free). We check if the magic pointer points to the address pointed to by the parameter before free. Here we use the second option:
First we add a magic pointer to the structure (and also modify BLOCK_SIZE):
Typedefstruct s_block *t_block;
Struct s_block {
Size_t size;/* data area size*/
T_block next;/* Pointer to the next block */
Int free; /* Is it a free block */
Int padding; / * padding 4 bytes, guarantee the length of the meta block is a multiple of 8 * /
Void*ptr; /* Magic pointer, pointing to data */
Char data[1]/* This is a virtual field indicating the first byte of the data block. The length should not be counted in meta */
};
Then we define a function that checks the validity of the address:
T_block get_block(void*p){
Char*tmp;
Tmp = p;
Return(p = tmp -= BLOCK_SIZE);
}
Int valid_addr(void*p){
If(first_block){
If(p > first_block && p < sbrk(0)){
Return p ==(get_block(p))->ptr;
}
}
Return0;
}
When malloc and free are repeated multiple times, the entire memory pool may generate a lot of fragmented blocks. These blocks are small, often unusable, and even many fragments are connected together. Although the total can satisfy some malloc requirements, it is divided into many. A small block can't fit, this is the fragmentation problem.
In a simple solution, when a block is freed, if it finds that its neighboring block is also free, the block and the adjacent block are merged. To satisfy this implementation, you need to change s_block to a doubly linked list. The modified block structure is as follows:
Typedefstruct s_block *t_block;
Struct s_block {
Size_t size;/* data area size*/
T_block prev;/* Pointer to the previous block */
T_block next;/* Pointer to the next block */
Int free; /* Is it a free block */
Int padding; / * padding 4 bytes, guarantee the length of the meta block is a multiple of 8 * /
Void*ptr; /* Magic pointer, pointing to data */
Char data[1]/* This is a virtual field indicating the first byte of the data block. The length should not be counted in meta */
};
The merge method is as follows:
T_block fusion(t_block b){
If(b->next && b->next->free){
B->size += BLOCK_SIZE + b->next->size;
B->next = b->next->next;
If(b->next)
B->next->prev = b;
}
Return b;
}
With the above method, the idea of ​​free implementation is clearer: first check the legality of the parameter address, if it is not legal, do nothing; otherwise, the free of this block is marked as 1, and if possible, with the latter Block is merged. If the current block is the last block, the break pointer is rolled back to release the process memory. If the current block is the last block, the break pointer is rolled back and the first_block is set to NULL. The implementation is as follows:
Void free(void*p){
T_block b;
If(valid_addr(p)){
b = get_block(p);
B->free =1;
If(b->prev && b->prev->free)
b = fusion(b->prev);
If(b->next)
Fusion(b);
Else{
If(b->prev)
B->prev->prev = NULL;
Else
First_block = NULL;
Brk(b);
}
}
}
3.2.8 Realloc implementation
In order to implement realloc, we first need to implement a memory copy method. Like the calloc, for efficiency, we copy in 8-byte units:
Void copy_block(t_block src, t_block dst){
Size_t*sdata, *ddata;
Size_t i;
Sdata = src->ptr;
Ddata = dst->ptr;
For(i =0;(i *8)< src->size &&(i *8)< dst->size; i++)
Ddata[i]= sdata[i];
}
Then we started to implement realloc. A simple (but inefficient) method is to malloc a piece of memory and then copy the data. But we can do it more efficiently, and we can consider the following aspects:
If the data area of ​​the current block is greater than or equal to the size required by realloc, no action is taken.
If the new size gets smaller, consider split
If the data area of ​​the current block cannot satisfy the size, but the subsequent block is free and can be satisfied after the merge, consider doing the merge.
Here is the implementation of realloc:
Void*realloc(void*p,size_t size){
Size_t s;
T_block b, new;
Void*newp;
If(!p)
/* According to the standard library documentation, when p is passed NULL, it is equivalent to calling malloc */
Return malloc(size);
If(valid_addr(p)){
s = align8(size);
b = get_block(p);
If(b->size >= s){
If(b->size - s >=(BLOCK_SIZE +8))
Split_block(b,s);
}else{
/* See if consolidation is possible*/
If(b->next && b->next->free
&&(b->size + BLOCK_SIZE + b->next->size)>= s){
Fusion(b);
If(b->size - s >=(BLOCK_SIZE +8))
Split_block(b, s);
}else{
/* new malloc */
Newp = malloc (s);
If(!newp)
Return NULL;
New= get_block(newp);
Copy_block(b,new);
Free(p);
Return(newp);
}
}
Return(p);
}
Return NULL;
}
3.3 Legacy issues and optimization
The above is a relatively simple, but initially available malloc implementation. There are a lot of possible optimization points left behind, such as:
Compatible with both 32-bit and 64-bit systems
When assigning large, fast memory, consider using mmap instead of sbrk, which is usually more efficient
It is conceivable to maintain multiple linked lists instead of singles, and the block size in each linked list is in a range, such as an 8-byte linked list, a 16-byte linked list, a 24-32-byte linked list, and the like. At this point, you can assign according to the size to the corresponding linked list, which can effectively reduce the fragmentation and improve the speed of querying the block.
It can be considered that only the free block is stored in the linked list, and the allocated block is not stored, which can reduce the number of times of finding the block and improve the efficiency.
There are many possible optimizations, which are not repeated here. Attached below are some references, and interested students can study more deeply.
4 Other references
This article makes extensive reference to the A malloc Tutorial, some of which are directly referenced in the text and code.
Computer Systems: A Programmer's Perspective, 2/E has a lot of places to look into
About the virtual memory model of Linux, Anatomy of a Program in Memory is a good reference, and the author also has a How the Kernel Manages Your Memory for the virtual memory management part of the Linux kernel.
For real-world malloc implementations, you can refer to the implementation of glibc
Suizhou simi intelligent technology development co., LTD , https://www.msmsmart.com