Shulou(Shulou.com)05/31 Report--

This article mainly introduces the meaning of Linux physical memory fragmentation, which is very detailed and has a certain reference value. Friends who are interested must read it!

I. Overview of external fragmentation of Linux physical memory

What is Linux physical memory fragmentation? there are two types of Linux physical memory fragmentation:

1. Physical in-memory fragmentation: the unused part of the memory space allocated to the user.

For example, a process needs to use 3Kbytes physical memory, so it requests memory equal to 3Kbytes from the system, but because the smallest particle of the Linux kernel partner system algorithm is 4Kbytes, it allocates 4Kbytes memory, so the unused memory of 1K bytes is memory fragments.

Linux physical in-memory fragmentation

two。 External fragmentation of physical memory: small blocks of memory that cannot be used in the system.

For example, the remaining memory of the system is 16K bytes, but the 16K bytes memory is composed of four 4K bytes pages, that is, the 16K physical page frame number # 1 is not contiguous. In the case of 16K bytes memory left in the system, the system can not successfully allocate more than 4K continuous physical memory, which is caused by external memory fragmentation, which is described in this paper.

Note: # 1 physical page frame number: Linux physical memory is managed by pages, and each page is numbered, called page frame number. If there are two consecutive physical pages, the page frame number is continuous.

External fragments of Linux physical memory

II. Linux physical memory management framework

Before you explain the context of external fragmentation of physical memory, you need to understand how Linux manages physical memory? the Linux kernel uses buddy system allocation, the famous partner system allocator.

1. Design ideas

The core idea of the partner system allocator is to divide the free pages of the system into 11 block linked lists, each of which manages pages with continuous physical page frame numbers of 64128256512 and 1024 physical pages respectively. Each page size is 4K bytes,buddy managed block sizes range from 4K bytes to 4m bytes, increasing in multiples of 2.

Linux physical memory Management Framework Diagram

two。 Management logic

Linux's framework for physical page management is shown in the figure above. Because this article describes external fragments of physical memory, this article only makes a simple analysis of the partner system, does not involve specific details, and does not elaborate on per cpu pageset and other contents. If readers are interested, you can refer to the kernel source code.

Linux divides physical memory into different node and zone to manage:

Node: in order to support the NUMA structure, that is, CPU has different access speed to different memory clusters, Linux designs the node structure, which divides the physical memory into multiple memory nodes to manage; for the UMA structure, there is only one node node.

Zone: in order to be compatible with the hardware limitations of different platforms, such as the hardware bus access of the 80x86 architecture, Linux divides the memory under the node node into multiple zone; currently on the ARM platform, multiple zone management is no longer necessary.

The memory under the zone snap-in is managed by dividing the memory into 11 block linked lists through the free_area array:

The free_area array has a total of 11 indexes, each of which manages block linked lists of different sizes.

Free_area [0] manages memory in 2 ^ 0 pages, that is, 4K byte memory

Free_area [1] manages a physical page with a frame number of 2 ^ 1, that is, 8K bytes memory

And so on.

The memory managed by free_area is also subdivided into various types, such as immovable pages and removable pages, and each type of page type corresponds to a free_list linked list that links to the page structure.

When allocating a page, the steps for the partner system to get the page are as follows: (do not consider the slow path of memory)

According to the allocated page type, find the corresponding memory node node and memory management unit zone

The free_area structure of the corresponding size found according to the allocated page size

According to the type of assigned page, find the corresponding free_list linked list and assign the page.

When releasing the page to the partner system, buddy releases the page as follows:

According to the allocated page type, find the corresponding memory node node and memory management unit zone

Determine whether there is a free memory block connected to the frame number of the physical page, which can be merged with the freed memory block into a larger block of memory, the condition of merging:

Physical frames must all be continuous

Same type and same size.

The physical address of the first page of the merged block memory satisfies a multiple of "2* block size * 4K".

The free_area structure of the corresponding size found based on the size of the released page or the size of the merge

According to the type of release page, find the corresponding free_list linked list and release the page.

III. Linux measures for external fragmentation of physical memory

From the "Linux physical memory management architecture", it can be found that the partner system memory management framework can effectively improve the external fragmentation of physical memory, because the partner system has the following two management logic, which can reduce the generation of external fragmentation:

There are small linked lists in small blocks to reduce the probability of large linked lists being contaminated.

The logic that tries to integrate large chunks of memory when memory is released, which helps to synthesize large chunks of memory.

In addition, the kernel supports the following measures to improve external fragmentation of physical memory (list only the main mechanisms):

1.memory compaction

(1) the principle of memory normalization

Linux physical page warping mechanism, similar to disk finishing, mainly applies the kernel page migration mechanism, which is a method to free up continuous physical memory after migrating removable pages.

Suppose there is a very small memory domain as follows:

Blue indicates free pages, white indicates pages that have been allocated, and you can see that the free pages (blue) in the memory domain above are very scattered and cannot allocate more than two pages of continuous physical memory.

The kernel runs two separate scan actions: the first scan starts at the bottom of the memory domain and records the allocated MOVABLE pages in a list while scanning:

In addition, the second scan starts at the top of the memory domain, scans for free page locations that can be the target of page migration, and then records them in a list:

When the two scans meet in the middle of the domain, it means that the scan is over, and then migrate the allocated page from the left scan to the free page on the right, and the left side forms a continuous piece of physical memory to complete the page tidiness.

(2) usage

If you want to turn on memory tidiness, the kernel needs to turn on the relevant configuration (default is y)

After opening the above configuration, the trigger of memory normalization is automatic, and the ways to trigger memory normalization are as follows: when the process tries to allocate high-level memory and finishes direct_reclaim#1 (not analyzing costly_order for the time being), the system will judge whether memory normalization will be triggered based on the memory remaining.

Note: # 1direct_reclaim: the process finds insufficient memory when allocating memory and starts the direct memory recovery operation. In this mode, the relationship between allocation and recycling is synchronous, that is, the process that allocates memory will be blocked by waiting for memory to be reclaimed.

The kernel also provides an API for users to trigger regular actions, as shown below:

/ proc/sys/vm/compact_memory

Simply writing a value to this node triggers memory normalization for all node-managed memory in the system.

2.kcompactd

(1) the design principle of kcompact

Kcompactd is a background process with a regular kernel, which differs from memory compaction in:

The trigger way of memory compaction is that after memory allocation enters direct_reclaim (do not analyze the costly_order situation for the time being), the system will judge whether to trigger memory normalization according to the remaining memory, or whether the user will trigger it manually.

Kcompactd actively triggers memory normalization when it wakes up kswapd or kswapd to go to sleep.

The trigger path of kcompactd is as follows: there are two main ways:

The normalization is triggered before waking up kswapd. The condition is that the direct_reclaim,node memory node is balanced and the number of kswapd failures is greater than that of MAX_RECLAIM_RETRIES (default 16).

When kswapd is about to go to sleep:

(2) usage

If you want to turn on memory tidiness, the kernel needs to turn on the relevant configuration (default is y)

3. Other optimization ideas

The kernel is constantly optimized, so why does Linux still have external fragmentation of physical memory? That's because external fragmentation of physical memory, although it can be continuously optimized, cannot be eradicated. I think there are two main reasons for the physical fragmentation of the current kernel:

Immovable pages pollute the memory environment, resulting in page alignment failure

As the system continues to apply for and release pages, the physical memory page frame number assigned by the partner system becomes more random, resulting in a higher probability of memory partition and a higher degree of fragmentation, as described in 3.2.

In view of the above two reasons, the following optimization measures may achieve certain optimization results:

(1) reduce the pollution of UNMOVABLE pages to the memory environment

Limit the behavior of stealing pages that cannot be moved

The fallback mechanism, also known as page theft mechanism, is supported in Linux memory allocation. The purpose of this mechanism is to avoid the remaining imbalance of the page type of the same zone management unit. For example, the same zone,A page type has more free memory, but the B page type is very short of free memory. If there is no page theft mechanism, allocating the B page type will enter the slow path of memory allocation. With the page theft mechanism, in the same zone management unit, if the UNMOVABLE type does not have free pages, but the MOVABLE type pages still have free pages, the page theft mechanism supports the allocation of pages to list_ headers [unmanned] when the pages are not allocated.

The following array identifies the types of pages that can be stolen by various page types. For example, the first line indicates that UNMOVABLE pages can steal pages of RECLAIMABLE and MOVABLE types, and others are similar.

If the immovable pages steal pages frequently, the immovable pages will quickly pollute the memory environment, especially the memory of the movable pages, which will have a great impact on the success rate of memory normalization. Based on the above situation, we can add the judgment of allocation size limit to the mechanism of page theft, and immovable pages are allowed to steal pages only when large blocks of memory are allocated, so as to reduce the pollution of immovable pages to the memory environment.

Active repayment after the immovable page steals the page

This method is mainly a compensation method after immovable pages steal pages. If an immovable page steals a page, we record the page in a list, and when there are free pages in subsequent immovable page types, we migrate the stolen page back to the immovable page, so as to reduce the pollution of the immovable page.

(2) reduce the randomness of assigning page frame numbers.

Suppose there is a small memory domain as follows, which of the following two memory allocation methods will lead to severe memory fragmentation?

The page is assigned from the head to the tail

Pages are randomly assigned from any location.

Obviously, the second way of memory allocation is less friendly to external memory fragmentation, which is also a problem that the partner system has not solved at present. Although the partner system plans memory into memory blocks of various sizes to allocate small memory in small linked lists and try not to pollute large memory linked lists, there is no way to guarantee that small blocks of memory are allocated in which page frame range of physical memory. The longer the system runs, the more random the physical page frame number allocated to small blocks of memory becomes, the higher the probability of fragmentation.

Reservation method

According to this situation, the corresponding optimization can be made by the way of reservation.

A certain amount of memory is reserved for small blocks of memory allocation. after this optimization measure, the randomness of physical page frame numbers allocated by small blocks of memory can be effectively reduced, thus reducing the probability of small blocks of memory polluting the memory environment.

A certain amount of memory is reserved for large blocks of memory allocation. after this optimization measure, the probability of reserved memory being contaminated by small blocks of memory will be reduced, which can improve the success rate of reserved memory allocation of large blocks of memory.

In addition, there are still many optimization measures to reduce the randomness of the frame number of the partner system allocation page. Follow-up will carry out a special article on this part of the optimization according to the needs. If the reader is interested, you can consult it then.

The above is all the contents of the article "what does external fragmentation of Linux physical memory mean?" Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

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.