LinuxMalloc Analysis - From User Space to Kernel Space

This article describes the implementation of malloc and its malloc in the heap expansion operation, and analyzes how the virtual address to physical address is how to achieve mapping.

ordeder original, original link: http://blog.csdn.net/ordeder/article/details/41654509

1 background knowledge

1.1 user space of the process < Br>

Figure 1: Source http://www.open-open.com/lib/view/open1409716051963.html

The structure is defined by the process task_struct.mm_struct mm_struct is defined as follows:

? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 struct mm_struct { struct vm_area_struct * mmap ; /* list of VMAs */... pgd_t * pgd; //for address mapping atomic_t mm_users; /* How many users with user space? */atomic_t mm_count; /* How many references to "struct mm_struct" ( Users coun t as 1) */int map_count; /* number of VMAs */... //Describe the segment distribution of user space: data segment, code segment, stack segment unsigned long start_code, end_code, start_data, end_data; unsigned long start_brk, Brk, start_stack; unsigned long arg_start, arg_end, env_start, env_end; unsigned long rss, total_vm, locked_vm; ... };

The startxxx and endxxx in the structure describe the process user space data segment Address. For heap space, start_brk is the starting address of the heap space, and the heap is scaled up. For the extension of the process heap space, brk records the top position of the heap. The address space (the variable being used) of the space dynamically applied by the process is mapped, and these address spaces are recorded in the linked list struct vm_area_struct * mmap.

1.2 Address Mapping

Mapping of Virtual Addresses and Physical Addresses: http://blog.csdn.net/ordeder/article/details/41630945

< H1> 2 malloc and free

malloc is the function interface for user space heap extension. This function is a C library belonging to the glibc library function that encapsulates the relevant system call (brk()). Instead of a system call (the system can have no sys_malloc(). If you talk about the operations of the system kernel involved in the malloc function, then the whole can be divided into user space level and kernel space level.

2.1 User layer < Br>

The source code for malloc is visible at http://repo.or.cz/w/glibc.git/blob/HEAD:/malloc/malloc.c

Malloc and free It works at the user level, which provides the user with an interface that is more convenient to manage the heap. Its main job is to maintain a free heap space buffer list. The buffer can be expressed in the following data structure:

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

< Br>

The simplified version of the free buffer list is shown below. The head is the malloc_chunk structure described above. The memory area of ​​the size of the next size is the data area corresponding to the chunk.

[malloc]

Whenever a process calls malloc, it first looks for a memory block of sufficient size in the heap buffer to allocate to the process (the block in the buffer has the first hit and Best hit two algorithms). If the freechunklist can no longer satisfy the required chunk, then malloc will expand the heap of the process space by calling the system call brk(), create a new chunk on the newly expanded heap space and add it to the freelist. This process is equivalent to The process batch wants the system to apply for a piece of memory (the size may be much larger than the actual demand).

The address returned by malloc is the first address in the chunk used to store data, ie: chunk + sizeof(chunk)

A simple pseudo-first hit malloc Code: