Each Linux process has its own dedicated address space dynamically translated into physical memory address space by the MMU (and the kernel) [1]. To each individual process, the view is as if it alone has full access to the system’s physical memory [2]. More importantly, the address space of even a single process can be much larger than physical memory. However, the memory usage of each process is bounded with Linux resource limitation (via setrlimit()).
The space is divided into several parts, including text, data, heap and stack, etc. Stack and heap are the two parts we’ll talk about. At the time of creation, the system creates heap and stack segment for processes. While stack is the reserved memory as scratch space for thread execution, heap is memory set aside for dynamic allocation. Each thread gets a stack, while there’s typically only one heap for the application. The OS allocates the stack for each system-level thread when the thread is created, and the stack size is predetermined in creation. Typically, the OS is called by the language runtime to allocate the heap for the application. The heap size is set on application startup, but it can grow by calling allocators to request more memory from OS. [3]
In the runtime, dynamic memory management is operated on heap. Standard C functions malloc() and free() are used to allocate and deallocate memory blocks. malloc() is a library call, not a system call, which directly deals with paged virtual memory instead of physical memory (which is handled by the kernel). As the system creates heap and stack segment for processes at the time of creation, malloc() already has some memory to work with without having to call the OS for every memory request from the program. If more memory is needed (either due to malloc() or due to stack growing), then a system call brk()/sbrk()/mmap() is made to obtain a contiguous (w.r.t virtual memory address) chunk of memory, which the malloc() further slices and dices in smaller chunks and hands out to the application. [3,4]
Various different implementations of malloc() attempt to satisfy any given request from the memory which has already been allocated to the process. And, these allocators are categorized mainly by how they keep track of the free blocks that they can use to parcel out memory to applications. Main categories are first-fit, best-fit and worst-fit, etc. [5]
Memory allocation inside kernel
Actual physical memory is managed by Linux kernel. The kernel treats physical pages as the basic unit of memory management. Although the processor’s smallest addressable unit is usually word (or even a byte), the MMU typically deals in pages. The MMU manages page tables with page-sized granularity. [2] The space in between the heap and the stack is unallocated space, therefore the top of the heap is often referred to as the “break point” because this is where the memory space is split. As more dynamic memory is needed, the application must inform the OS to move up the break point to allocate more memory for the process, thus increasing the heap size. The allocation is usually achieved by brk()/sbrk(). On a call to brk(), the Linux kernel performs a few checks and then allocates the new memory for the process. First, the kernel aligns the old and the new break point to be on page boundaries. A page (usually 4KB) is the smallest unit of memory that the OS will give to any process. Then, the system call checks the limits and the kernel verifies that it is safe to allocate the required memory, and finally the kernel calls do_brk() function to increase the memory for the process. Each process has a map/page-table to take a certain range of addresses in the processes’ address space and to map it physical memory. When the process calls brk(), the OS increases the map size for the heap, thus giving the process more memory to use.
When the map size is increased, the new pages that are mapped into the address space do not actually exist, i.e., no physical pages are allocated for the new mapping. The OS, by increasing the map size, only provides a mapping between the new addresses in the process space and the memory that those pages will occupy when they are used.
Summary of malloc() workflow
The malloc() calls an internal helper, chunk_alloc(), to find the block to return to the user. This helper is the function that looks through the bins for a match to return. If its cannot find a suitable match, it calls malloc_extend_top(), another helper function, that actually calls sbrk().
Once the memory is retrieved from the OS, chunk_alloc() splits off the piece that is required for the current location. It then adds the remainder to the appropriate bin for future use and returns the new block to malloc(), which then returns that block to the user. As it turns out, most of the work that malloc() does deals with deciding how to manage memory that has already been allocated by the OS.
[1] A Malloc Tutorial, 2009
[2] http://www.makelinux.net/books/lkd2/?u=ch14
[3] http://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap
[4] http://cs.boisestate.edu/~amit/teaching/453/slides/memory-management-handout.pdf
[5] http://www.linux-mag.com/id/827/
本文地址：http://xnerv.wang/memory-allocation-mechanism-in-linux/
转载自：Memory Allocation Mechanism in Linux