Shulou(Shulou.com)06/02 Report--

Virtual memory of roaming computer system 1. Background

A typical computer system is shown in the following figure:

Allowing applications to use hardware directly can lead to abuse, and applications need to deal with complex hardware details and are prone to errors. So we introduced the operating system to manage hardware resources, as shown in the following figure:

In order to make it easier for applications to use hardware resources, the operating system further abstracts hardware resources, as shown in the following figure:

two。 Virtual memory

Virtual memory abstracts the storage devices accessed by the process into a huge array of bytes and encodes each byte with a unique address. It provides three important functions:

The main memory is regarded as a cache of address space stored on disk, thus improving the efficiency of the use of main memory. Provide a consistent address space for each process and simplify memory management. Protect the address space of each process from being destroyed by other processes.

Virtual memory works automatically behind the scenes without the intervention of application programmers, so why do we need to understand it? I want to understand that it can bring the following benefits:

Virtual memory is the core of computer system. It involves all aspects of the computer system (hardware exceptions, assemblers, linkers, loaders, shared objects, files, processes), and understanding it will help us better understand how the computer system works. The function of virtual memory is very powerful. It gives the application powerful functions, such as loading a file into memory without any display copy. Virtual storage is very dangerous. For writing programs such as cUniverse +, an error pointer can make the program crash immediately. Understanding it allows us to better avoid mistakes, or better locate the problem when an error occurs. 3. Virtual addressing

The process sees that it is a virtual address, but the information is stored in physical memory, so how does the system use the virtual address to obtain the byte information of the corresponding physical memory? In short, it can be divided into three steps:

CPU sends the virtual address to MMU (Memory Management Unit) MMU, translates the virtual address into a physical address, transmits it to main memory, and transfers the bytes corresponding to the physical address to CPU.

The specific process is shown in the following figure:

3.1. Page table

How does MMU translate virtual addresses into physical addresses?

OS divides physical memory and virtual memory into blocks of the same size (linux defaults to 4k) and calls them pages. At the same time, each process is assigned a page table, which is an array of page table entries (PTE), where each PTE records the mapping of virtual pages to physical pages.

A virtual address can be divided into two parts: virtual page number × × and virtual page offset VPO. Since the virtual page is the same size as the physical page, the virtual page offset is the physical page offset. The virtual page number is the index of the PTE in the page table, and the corresponding PTE stores the physical page number and valid bits (indicating whether the page has a corresponding physical page), so that MMU can find the physical page corresponding to the virtual page by querying PTE, and the physical address can be obtained by adding the virtual page offset, as shown below:

3.2. Multi-level page table

If each process has only one page table (assuming the physical page size is 4k), 4m memory is required for 32-bit systems (4 bytes per PTE); for 64-bit systems (actually only 48 bits are used for addressing), 256 gigabytes of memory is needed, which is too large. To solve this problem, we use a multi-level page table, such as the following figure:

In the multi-level page table, the page table size of all levels is the same, we take the linux level 4 page table as an example, then at least 4 page tables, suppose a page table 4k, a total of 16k; with the growth of process memory consumption, the number of k-level page tables increases linearly, because the number of other levels of page tables is much smaller than that of k-level page tables, so the total page table consumption memory pages are close to linear growth. Because the actual amount of memory consumed by the process is much less than 256T, the memory consumption of the page table is much less than that of the first-level page table.

4. Process memory layout

From the summary above, we know that each process has an independent virtual storage space, so is its layout regular? Let's take a 64-bit process under linux as an example, as shown in the following figure:

Linux organizes the user's virtual memory into a collection of segments. A segment is a contiguous piece of allocated virtual memory. Only virtual memory pages that exist in the segment can be accessed by the process.

# include int main () {char* p = (char*) malloc (1); while (1); return 0;}

After compiling the above code and running it, after getting the process PID through top, we can open the / proc/PID/maps file to view the memory layout of the process:

00400000-00401000 r-xp 00000000 fd:01 723899 / home/wld/test/a.out00600000-00601000 rmurmuri p 00000000 fd:01 723899 / home/wld/test/a.out00601000-00602000 rw-p 00001000 fd:01 723899 / home/wld/test/a.out0148c000-014ad000 rw-p 00000000 00:00 0 [heap] 7fb917267000-7fb917425000 r-xp 00000000 fd:01 1731435 / lib/x86_64-linux-gnu/libc-2.19.so7fb917425000-7fb917625000-p 001be000 fd:01 1731435 / lib/x86_64-linux-gnu/libc-2.19.so7fb917625000-7fb917629000 Rukyu p 001be000 fd:01 1731435 / lib/x86_64- Linux-gnu/libc-2.19.so7fb917629000-7fb91762b000 rw-p 001c2000 fd:01 1731435 / lib/x86_64-linux-gnu/libc-2.19.so7fb91762b000-7fb917630000 rw-p 00000000 00:00 07fb917630000-7fb917653000 r-xp 00000000 fd:01 1731443 / lib/x86_64-linux-gnu/ld-2.19.so7fb917835000-7fb917838000 rw-p 00000000 00:00 07fb917850000-7fb917852000 rw-p 00000000 00:00 07fb917852000-7fb917853000 r -- p 00022000 fd:01 1731443 / lib/x86_64-linux-gnu/ld-2.19.so7fb917853000-7fb917854000 rw-p 00023000 fd:01 1731443 / lib/x86_64-linux-gnu/ld-2.19.so7fb917854000-7fb917855000 rw-p 00000000 00:00 07ffe8b3e1000-7ffe8b402000 rw-p 00000000 00:00 0 [stack] 7ffe8b449000-7ffe8b44b000 Rmuri p 0000000000: 000 [vvar] 7ffe8b44b000-7ffe8b44d000 r-xp 00000000 00:00 0 [vdso] ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]

Each of the above lines represents a paragraph, and each paragraph has six columns, each of which means as follows:

The start address of this virtual address space-the end address. The properties of this virtual address space. Each attribute is represented by a field, r for readable, w for writable, x for executable, p and s for mutual exclusion, p for private segment, s for shared segment, and if there is no corresponding permission, use'- 'instead. For name mapping, represents the offset of the starting address of this segment of virtual memory in pages in the file. For anonymous mapping, it equals 0 or vm_start/PAGE_SIZE. The device number to which the mapping file belongs. For anonymous mapping, there is no device number because there is no file on disk, and it is always 00:00. For name mapping, it is the node number to which the device number mapping file of the mapped file belongs. For anonymous mapping, because there is no file on disk, there is no node number, which is always 00:00. For name mapping, the node number of the mapped file is, for name, the file name of the mapping. For anonymous mapping, it is the role of this virtual storage in the process. [stack] is used as a stack in a process, and [heap] is a heap. The rest of the case does not show 5. 5. Page fault exception handling

If MMU does not have a corresponding physical address when trying to translate a virtual address A, a page fault exception is triggered. This exception causes control to be transferred to the kernel's page fault exception handler, which then performs the following steps:

Is the virtual address legal? That is, whether the virtual address is within the address range of the assigned segment. If it cannot be found, a segment error will be triggered. Is the virtual address access you are trying to make legal? That is, whether the permission conforms to the permission of the segment in which it belongs. If there is no permission, a protection exception will be triggered. Assign physical pages and update page tables. When the page fault handler returns, CPU reexecutes the instruction that caused the page fault.

You can view the missing page break information for a process by executing either of the following commands

Ps-o majflt,minflt-C program_name

Ps-o majflt,minflt-p pid

The values majflt and minor represent the number of page-missing interruptions that have occurred since a process was started.

The difference between majflt and minflt is that majflt means that you need to read and write to the disk. It may be that the corresponding memory pages need to be load to the physical memory in the disk, or there may be insufficient physical memory at this time, so you need to eliminate some physical pages to the disk.

6. Memory mapping

Linux initializes the contents of this virtual storage segment by associating virtual intranets with files on a disk, a process called memory mapping (memory mapping). There are two kinds of memory mapping:

Named file mapping: a segment can be mapped to a contiguous portion of a normal disk file, such as an executable file. Anonymous file mapping: a segment can also be mapped to an anonymous file that is created by the kernel and contains all binary zeros.

# 6.1 shared objects

Memory mapping allows us to simply and efficiently load programs and data into virtual memory space. In practice, many processes map the same file to memory, such as the glic dynamic library, which is extremely wasteful if there are multiple copies in physical memory. We can eliminate waste by sharing object technology.

For private objects, we can use write-time copy technology to share physical memory pages.

6.2 can the thinking questions transmit information between processes through the global variables of the dynamic library? After process A uses the dynamic library S, updates the S version, and then starts process B using S, can process A still have normal access to the functions of S? 7. Dynamic memory allocation

There are many dynamic memory allocators in unix-like operating systems, such as ptmalloc (default for linux), tcmalloc (produced by google), and jemalloc (default for FreeBSD, NetBSD, and firefox). A detailed description of these three allocators can be found in http://www.360doc.com/content/13/0915/09/8363527_314549128.shtml.

This paper takes ptmalloc as an example to introduce dynamic memory allocation. Under linux, os provides two kinds of dynamic memory allocation brk and mmap. Ptmalloc uses brk mode for those with less than 128k memory, and mmap mode for those with more than 128k memory.

7.1. Mmap

For large memory, malloc will directly call the system function mmap to allocate memory and align it in the smallest unit of the physical page. Free directly calls the system function munmap to free memory.

7.2. Brk

The process has a pointer to the address at the top of the heap, and the system function brk can change the position of the pointer to change the size of the heap (the heap can be enlarged or shrunk). When an existing heap cannot allocate memory, brk expands the heap to allocate dynamic memory. When the top memory is freed, when the cut-free memory is greater than 128k, the heap will shrink, as shown in the following figure:

From the heap allocation release method above, we know that in fact, many small memory requests will not be immediately released to OS. In order to reuse this memory, the memory allocator needs an algorithm. Here is how to deal with ptmalloc.

7.3. Ptmalloc

Ptmalloc organizes each memory unit through the data structure of chunk. When we use malloc to allocate a piece of memory, the memory is recorded on glibc and managed in the form of chunk. You can think of it as a memory data structure when you write to the memory pool. The structure of chunk can be divided into chunk in use and free chunk. The basic items of the chunk in use are the same as those of the idle chunk data structure, but there will be some design tips that skillfully save memory.

Chunk in use:

The chunk pointer points to the address where the chunk starts; the mem pointer points to the address where the user memory block starts. When ptmalloc 0 indicates that the previous chunk is idle and prev_size is valid, it means that the previous chunk is in use, and that prev_size is invalid p is mainly used for merging memory blocks. The first block allocated by ptmalloc always sets p to 1 to prevent the program from referencing areas that do not exist. Ptmalloc 1 is assigned to the mmap mapping area; heap 0 is assigned to the heap area as a non-primary partition; Amal0 is allocated as the primary partition

The idle chunk structure reuses User data to hold two-way linked list pointers.

Ptmalloc maintains a total of 128bin. Each bins maintains a chunk of a bi-directional linked list of similar size.

From the list of bins shown above, when a user calls malloc, he can quickly find out whether the amount of memory that the user needs to allocate is on the maintained bin. If it is on a certain bin, he can find the appropriate chunk memory block for the user through a two-way linked list.

Fast bins . Fast bins is a high-speed buffer for bins, with about 10 fixed-length queues. When a user releases a chunk (usually small memory) that is not larger than max_fast (the default is 64), it will be placed on fast bins by default. The next time users need to apply for memory, they will first go to fast bins to see if there is a suitable chunk, and then they will go to the free chunk on bins. Ptmalloc iterates through fast bin to see if there is a suitable chunk to merge into bins. Unsorted bin . Is a buffer for bins. When the memory released by the user is larger than max_fast or the merged chunk of fast bins will enter into unsorted bin. When users malloc, they will first check unsorted bin to see if there is a suitable bin. If there is no suitable bin,ptmalloc, they will put the chunk on unsorted bin into bins, and then go to bins to find a suitable free chunk. Small bins and large bins. Small bins and large bins are really used to place chunk two-way linked lists. There is an 8-byte difference between each bin, and through the list above, you can quickly locate a free chunk of the right size. The first 64 are small bins with fixed length, and the last 64 are large bins with non-fixed length. Top chunk . Not all chunk will be put on bins. Top chunk is equivalent to the free memory at the top of the allocation area. When none of the bins meets the memory allocation requirements, it will be allocated on the top chunk. Mmaped chunk . When the allocated memory is very large (larger than the allocation threshold, the default is 128K) and needs to be mapped by mmap, it will be placed on mmaped chunk and returned to the operating system directly when the memory on mmaped chunk is released. 7.3.1. The memory allocation malloc process acquires the lock of the allocation area to prevent multi-thread conflicts. Calculate the actual chunk size of the memory that needs to be allocated. Determine the size of the chunk. If it is less than max_fast (64b), take the fast bins to query whether there is a suitable chunk, and if so, the allocation ends. Whether the chunk size is less than 512B, if so, look for chunk from small bins, and if appropriate, the allocation ends. Continue to search unsorted bins. If there is only one chunk on the unsorted bins and is larger than the chunk to be allocated, the cutting is carried out, and the remaining chunk continues to be thrown back to the unsorted bins;. If there is a size equal to the chunk to be assigned on the unsorted bins, it is returned and deleted from the unsorted bins; if a certain chunk size in the unsorted bins belongs to the range of small bins, it is put into the head of the small bins; if a chunk size in the unsorted bins belongs to the range of large bins, find a suitable position to put it. Look in large bins, find the chain header, reverse traverse the linked list until the first size is larger than the chunk to be allocated, and then cut it. If there is any remaining, put it in the unsorted bin, and the allocation ends. If the search fast bins and bins do not find a suitable chunk, then you need to manipulate top chunk to allocate (top chunk is equivalent to the remaining memory space of the allocation area). Determine whether the top chunk size meets the desired chunk size, and if so, separate a piece from the top chunk. If top chunk does not meet the demand, then top chunk needs to be expanded. On the primary partition, if the allocated memory is less than the allocation threshold (the default is 128k), use brk () to allocate a piece of memory directly; if the allocated memory is greater than the allocation threshold, you need mmap to allocate it; on the non-primary partition, use mmap directly to allocate a piece of memory. The memory allocated through mmap is put into mmap chunk, and the memory on mmap chunk is recycled directly to the operating system. 7.3.2. The memory release free process acquires the lock of the allocation area to ensure thread safety. If the free has a null pointer, it returns and does nothing. Determine whether the current chunk is the memory mapped by the mmap mapping area, and if so, simply munmap () to free the memory. In the previous data structures that have used chunk, we can see that there is M to identify whether it is mmap-mapped memory. It is determined whether the chunk is adjacent to the top chunk, and if so, it is merged directly with the top chunk (adjacent to the top chunk is equivalent to adjacent to the free memory block in the allocation area). Go to step 8 if the size of the chunk is greater than max_fast (64b), put in the unsorted bin, and check if there is a merge, there is a merge and is adjacent to the top chunk, then go to step 8; if there is no merge, then free. If the size of the chunk is less than max_fast (64b), putting it directly into the fast bin,fast bin does not change the state of the chunk. If there is no merge, then free; has a merge, go to step 7 in fast bin, and if the next chunk of the current chunk is also free, merge the two chunk and put them on top of the unsorted bin. If the merged size is greater than 64KB, the merge operation of fast bins will be triggered, the chunk in fast bins will be traversed and merged with the adjacent idle chunk, the merged chunk will be put into unsorted bin, and the fast bin will become empty. If the merged chunk and topchunk are adjacent, they will be merged into the topchunk. Go to step 8 to determine whether the size of the top chunk is greater than the mmap shrinkage threshold (default is 128KB), and if so, for the main allocation area, an attempt is made to return a portion of the top chunk to the operating system. Free is over. 7.4. Memory fragmentation

The main reason for low heap utilization is fragmentation, which occurs when there is unused memory but cannot be used to satisfy allocation requests. There are two forms of fragments:

Internal fragments: the allocated block is larger than the payload. There is often internal fragmentation when implementing a memory pool or managing memory yourself. External fragmentation: the free memory can be combined to meet the allocation requirements, but no single free block is large enough to satisfy the allocation request. At present, some good third-party allocators, such as tcmalloc and jemalloc, can solve the problem of external fragmentation very well. 7.5. Thinking questions

# Question1: will OS allocate 1 GB of physical memory immediately after the following code is run?

# include int main () {char* p = (char*) malloc (1024 / 1024 / 1024); while (1); return 0;}

# question 2: how much physical memory will be allocated by OS after the following code is run?

# include # include int main () {const size_t MAX_LEN = 1024 "1024" 1024; char* p = (char*) malloc (MAX_LEN); memset (p, 0, MAX_LEN/2); while (1); return 0;}

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.