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

This article mainly introduces Linux physical memory fragmentation example analysis, the article is very detailed, has a certain reference value, interested friends must read!

I. Overview of Linux physical memory fragmentation

What is Linux Physical Memory Fragmentation? Linux physical memory fragmentation includes two types:

Physical memory fragmentation: unused portion of memory space allocated to users

For example, the process needs to use 3K bytes of physical memory, so it applies to the system for a memory size equal to 3 K bytes, but since the minimum particle of the Linux kernel partner system algorithm is 4 K bytes, the allocated memory is 4 K bytes, so the memory that 1K bytes is not used is the memory fragment.

Physical out-of-memory fragmentation: refers to small blocks of memory in a system that cannot be utilized

For example, the remaining memory of the system is 16K bytes, but this 16K bytes memory is composed of four 4K bytes pages, that is, the physical page number #1 of 16K memory is not consecutive. In the case of 16K bytes of memory remaining in the system, the system cannot successfully allocate more than 4K of contiguous physical memory, which is caused by out-of-memory fragmentation.

Note: #1 physical page frame number: Linux physical memory is managed by pages, and each page is numbered, called page frame number, if it is two consecutive physical pages, its page frame number is consecutive.

Linux Physical Memory Management Framework

Before explaining the ins and outs of fragmentation out of physical memory, it is important to understand how Linux manages physical memory. The Linux kernel uses buddy system allocation, the famous buddy system allocator.

design ideas

The core idea of the partner system allocator is to divide the idle pages of the system into 11 block linked lists, and each block linked list manages 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 and 1024 pages with continuous physical page frame numbers. Each page size is 4K bytes, and buddy manages block sizes ranging from 4K bytes to 4M bytes in multiples of 2.

management logic

Linux on the physical page management framework as shown in the figure above, because this article describes the physical memory outside the fragment, so on the partner system this article only makes a simple analysis, does not involve specific details and does not elaborate on the per cpu page and other content, if the reader is interested, you can refer to the kernel source code.

Linux divides physical memory into nodes and zones:

Node: In order to support NUMA architecture, that is, CPU access speed to different memory clusters, Linux designed the node structure, the physical memory is divided into multiple memory nodes management; for UMA architecture, there is only one node. Zone: In order to be compatible with the hardware limitations of different platforms, such as the hardware bus access of the 80×86 architecture, Linux divides the memory under the node node into multiple zones; currently, on the ARM platform, multiple zone management is unnecessary.

The memory under the zone management unit is managed by dividing the memory into 11 block lists through the free_area array:

The free_area array has a total of 11 indexes, each of which manages a list of blocks of different sizes. free_area[0] manages memory units of 2^0 pages, i.e. 4K bytes of memory;free_area[1] manages memory units of 2^1 consecutive pages of physical page frame numbers, i.e. 8K bytes of memory;

and so on;

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

According to the allocated page type, find the corresponding memory node and memory management unit zone; according to the allocated page size, find the corresponding free_area structure; according to the allocated page type, find the corresponding free_list linked list, allocate the page;

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

According to the allocated page type, find the corresponding memory node and memory management unit zone; judge whether there is an idle memory block connected with the physical page frame number, which can be merged with the released memory block into a larger block memory. The merging conditions: the physical frames must be continuous; the same type and size; the physical address of the first page of the merged block memory meets the multiple of "2 block size 4K." According to the size of the released page or the size of the merge, find the corresponding size of the free_area structure; according to the type of the released page, find the corresponding free_list, and release the page; III. Linux measures for fragmentation outside physical memory

From "II. Linux Physical Memory Management Architecture", we can find 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 logics, which can reduce the generation of external fragmentation:

There is a small block list allocation in the small block, reducing the probability that the large block list is contaminated; the logic that tries to integrate into the large block memory when the memory is released is helpful to the synthesis of the large block memory;

In addition to this, the kernel supports the following measures to improve out-of-physical memory fragmentation (to name only the main mechanisms):

memory compaction

(1)memory regularization principle

Linux physical page organization mechanism, similar to disk defragmentation, 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) of the memory field above are very fragmented and cannot allocate more than two pages of contiguous physical memory.

To demonstrate how memory regularization works in a simplified way, the kernel runs two separate scans: The first scan starts at the bottom of the memory domain and records allocated MOVABLE pages into a list as it scans:

In addition, the second scan starts at the top of the memory field and scans the free page locations that can be used as page migration targets, 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 the allocated pages scanned on the left are migrated to the free pages on the right, forming a continuous physical memory on the left, completing the page alignment.

(2)use method

To turn on memory regularization, the kernel needs to turn on the relevant configuration (y by default)

After the above configuration is enabled, the triggering of memory regularization is automatic, and the ways to trigger memory regularization are as follows: when the process tries to allocate high-level memory and fails to meet direct_reclaim#1(temporarily not analyzing the costly_order situation), the system will judge whether to trigger memory regularization according to the remaining memory;

Note: #1direct_reclaim: When the process allocates memory, it finds that there is insufficient memory and starts the direct memory reclamation operation. In this mode, the allocation and reclamation are synchronous, that is, the process allocating memory will be blocked because it waits for memory reclamation.

The kernel also provides interfaces for users to trigger regular actions, such as:

/proc/sys/vm/compact_memory

Just writing to this node triggers memory consolidation of all node managed memory in the system.

kcompactd

(1)kcompact design principle

kcompactd is a kernel structured background process, which differs from memory compaction in that:

The triggering way of memory compaction is that after memory allocation enters direct_reclaim(the situation of costly-order is not analyzed temporarily), the system will judge whether to trigger memory consolidation according to the remaining memory, or the user will trigger it manually;

kcompactd actively triggers memory regularization when kswapd wakes up or kswapd goes to sleep.

The trigger path for kcompactd is as follows: There are two main paths:

Regularization is triggered before waking kswapd. The triggering conditions are: direct_reclaim is not supported in this allocation, node memory nodes are balanced, and the number of kswapd failures is greater than MAX_RECLAIM_RETRIES(default 16).

kswapd is about to go to sleep:

(2)use method

To turn on memory regularization, the kernel needs to turn on the relevant configuration (y by default)

Other optimization ideas

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

Immovable pages pollute the memory environment, resulting in page regularization failure;

As the system continues to request and release pages, the physical memory page frame numbers allocated by the partner system become more random, resulting in a higher probability of memory fragmentation and a higher degree of fragmentation, as described in 3.2.

For the above two reasons, the following optimization measures may achieve certain optimization effects:

(1)Reduce UNMOVABLE page pollution memory environment

Limit page stealing behavior that cannot be moved

Linux memory allocation supports fallback mechanism, also known as page stealing mechanism. This mechanism is to avoid the imbalance of page types remaining in the same zone management unit. For example, in the same zone, page type A has more free memory, while page type B has very little free memory. If there is no page stealing mechanism, the allocation of page type B will enter the slow path of memory allocation. There is a page stealing mechanism. In the same zone management unit, if UNMOVABLE type has no free pages, but MOVABLE type pages still have free pages, the page stealing mechanism supports allocating pages to list_head[MOVABLE] when list_head[UNMOVABLE] cannot allocate pages.

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

If the non-removable pages frequently steal pages, the non-removable pages will soon pollute the memory environment, especially the memory of the removable pages, and the impact on the success rate of memory regularization is relatively large. Based on the above situation, we can add the judgment of allocation size limit to the mechanism of stealing pages, and only large block memory allocation of immovable pages is allowed to steal pages, so as to reduce the pollution of immovable pages to the memory environment.

Immovable type page after stealing page active repayment

This method is mainly a compensation method after stealing pages from immovable pages. If an immovable page steals a page, we record the page in a list, and when there are idle pages in the following immovable page types, the stolen page is migrated back to the immovable page, thereby reducing the pollution of the immovable page.

(2)Reduce randomness in assigning page frame numbers

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

Pages are allocated from the head to the tail; pages are allocated randomly from anywhere.

Obviously the second memory allocation is less friendly to out-of-memory fragmentation, which is a problem that partner systems do not currently solve. Although the partner system plans the memory into memory blocks of various sizes, so that small memory allocations are allocated in small block lists, and the large block memory list is not polluted as much as possible, there is no way to ensure that small blocks of memory are allocated in which page frame range of physical memory. The longer the system runs, the more random the allocation of physical page frame numbers for small blocks of memory, and the higher the probability of fragmentation.

reservation method

According to this situation, corresponding optimization can be carried out by way of reservation.

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

A certain amount of memory is reserved for block memory allocation. After the optimization measure, the probability that the reserved memory is polluted by small blocks of memory will be reduced, and the success rate of block memory allocation by reserved memory can be improved.

The above is "Linux physical memory fragmentation example analysis" all the content of this article, thank you for reading! Hope to share the content to help everyone, more relevant knowledge, welcome to pay attention to 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.