The Master said, “Aim at the tao, according to the virtue, according to the benevolence, and swim in the arts.” Analects of Confucius: A review

A hundred blog series. This paper is: the v17. Xx HongMeng kernel source code analysis (physical memory) | how to manage physical memory

Memory management:

  • V11. Xx HongMeng kernel source code analysis (memory allocation) | what memory allocation
  • V12. Xx HongMeng kernel source code analysis (memory management) | what is virtual memory panorama
  • V14. Xx HongMeng kernel source code analysis (memory assembly) | who is the foundation of virtual memory implementation
  • V15. Xx HongMeng kernel source code analysis (memory mapping) | virtual memory deficiency in where
  • V16. Xx HongMeng kernel source code analysis rules (memory) | what memory management in the tube
  • V17. Xx HongMeng kernel source code analysis (physical memory) | how to manage physical memory

How do I initialize physical memory?

The Hongmeng kernel physical memory adopts segment-page management. Let’s take a look at the two main structures. The meaning of each member variable of the structure has been annotated, please understand the source code.

#define VM_LIST_ORDER_MAX    9    // number of partner algorithm groups, from 2^ 0,2 ^1... , 8 (2 ^ 256 * 4 k) = 1 m
#define VM_PHYS_SEG_MAX    32    // A maximum of 32 segments are supported

typedef struct VmPhysSeg {// Physical segment descriptor
    PADDR_T start;            /* The start of physical memory area */ // The start address of the physical memory segment
    size_t size;              /* The size of physical memory area */ // Size of the physical memory segment
    LosVmPage *pageBase;      /* The first page address of this area */ // Address of the first physical page box in this paragraph
    SPIN_LOCK_S freeListLock; /* The buddy list spinlock */    // Partner algorithm spin lock, used to operate freeList lock
    struct VmFreeList freeList[VM_LIST_ORDER_MAX];  /* The free pages in the buddy list */ 2^ 0,2 ^1,... , 2 ^ VM_LIST_ORDER_MAX
    SPIN_LOCK_S lruLock;  // Spin lock for displacement, used to operate lruList
    size_t lruSize[VM_NR_LRU_LISTS];  //5 double loop linked list size, so convenient to get size
    LOS_DL_LIST lruList[VM_NR_LRU_LISTS]; // Page replacement algorithm, 5 double-loop linked list headers, which respectively describe the five different types of linked lists
} LosVmPhysSeg;


// Note: there are no virtual addresses in vmPage, only physical addresses
typedef struct VmPage { // Physical page frame descriptor
    LOS_DL_LIST         node;        /**< vm object dl list */ G_vmPhysSeg [segID]->freeList[ORDER] physical page-box list
    UINT32              index;       /**< vm page index to vm object */ // Index position
    PADDR_T             physAddr;    /**< vm page physical addr */  // Start physical address of the physical page box. It can only be used for calculation, but not for operation (read/write data ==).
    Atomic              refCounts;   /**< vm page ref count */   // Number of references, the shared memory will be referenced multiple times
    UINT32              flags;       /**< vm page flags */    // Page tags, can have multiple tags at the same time (shared/reference/active/locked ==)
    UINT8               order;       /**< vm page in which order list */ // the number of sequences placed in the partner algorithm (2^ 0,2 ^ 1,2 ^2,... , 2 ^ order)
    UINT8               segID;       /**< the segment id of vm page */ // Segment ID
    UINT16              nPages;      /**< the vm page is used for kernel heap */ // Assign pages, indicating that successive pages from this page will be allocated as a block
} LosVmPage;// Note: The relationship between nPages and order indicates that the order is equal to 3 when the request is assigned to 5 pages, because only 2^3 can satisfy a 5 page request
Copy the code

Understanding them is key to understanding physical memory management, especially LosVmPage, which is visible throughout the entire memory module code. The kernel allows a maximum of 32 segments to be managed by default.

Section page management is simply to cut the physical memory into a section, each section and then cut into the unit of 4K physical page frame, page is the operation unit in the kernel layer, the allocation of physical memory, replacement, page missing, memory sharing, file cache read and write, are based on the page as a unit, so LosVmPage is very important, very important!

Each variable in a structure represents a function point, and LOS_DL_LIST frequently appears in the structure. Bidirectional lists are the most important structure in the kernel, and its importance was specifically discussed at the beginning of this series.

RefCounts specifies the number of times a page is referenced by a process. When refCounts is greater than 1, the page is owned by multiple processes. When equal to 0, no process is in use and can be released.

For those of you who are familiar with JAVA, this looks like JAVA’s memory reclamation mechanism. At the kernel level, the concept of references applies not only to memory modules, but also to other modules, such as file/device modules, which are also shared. These modules are not explained here, but will be covered in subsequent chapters.

How did the paragraph start? The solution provider needs to manually configure, there are static global variables, hongmeng default configuration of only one section.

struct VmPhysSeg g_vmPhysSeg[VM_PHYS_SEG_MAX];// Array of physical segments, up to 32 segments
INT32 g_vmPhysSegNum = 0; / / the total number of segments
LosVmPage *g_vmPageArray = NULL;// Physical page box array
size_t g_vmPageArraySize;// Total number of physical page frames


/* Physical memory area array */
STATIC struct VmPhysArea g_physArea[] = {// There is only one region, i.e. only one segment is generated{.start = SYS_MEM_BASE,#define SYS_MEM_BASE DDR_MEM_ADDR, 0x80000000Size = SYS_MEM_SIZE_DEFAULT,// The total size of the physical memory 0x07F00000}};Copy the code

With segments and global variables, you can initialize memory. OsVmPageStartup is the initialization of physical memory, which is called by OsSysMemInit, the overall system memory initialization. Go straight to the code.

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * to complete initialization for physical memory as a whole, this function must be run under the real mode 1. G_vmPageArray to store LosVmPage Divided in 4 k pages of physical memory stored in the array. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
VOID OsVmPageStartup(VOID)
{
    struct VmPhysSeg *seg = NULL;
    LosVmPage *page = NULL;
    paddr_t pa;
    UINT32 nPage;
    INT32 segID;

    OsVmPhysAreaSizeAdjust(ROUNDUP((g_vmBootMemBase - KERNEL_ASPACE_BASE)， PAGE_SIZE));// Calibrate g_physArea size

    nPage = OsVmPhysPageNumGet(a);// Get the total pages of g_physArea
    g_vmPageArraySize = nPage * sizeof(LosVmPage);// Total page table size
    g_vmPageArray = (LosVmPage *)OsVmBootMemAlloc(g_vmPageArraySize);// Apply for memory in real mode. The MMU has not been initialized

    OsVmPhysAreaSizeAdjust(ROUNDUP(g_vmPageArraySize PAGE_SIZE));//

    OsVmPhysSegAdd(a);// Complete the initialization of the segment
    OsVmPhysInit(a);// Add the free list and set the replacement algorithm, LRU(most recently unused) algorithm

    for (segID = 0; segID < g_vmPhysSegNum; segID++) {// Traverse the physical segment, cutting the segment into pages
        seg = &g_vmPhysSeg[segID];
        nPage = seg->size >> PAGE_SHIFT;// Total pages of this paragraph
        for (page = seg->pageBase， pa = seg->start; page <= seg->pageBase + nPage;// Calculate the physical address of each page boxPage++, pa += PAGE_SIZE) {OsVmPageInit(page， pa， segID);// Initialize the physical page box, noting that the physical address of each page is different
        }
        OsVmPageOrderListInit(seg - > pageBase nPage);// The partner algorithm initializes and adds all pages to the free linked list for allocation}}Copy the code

With the Chinese comments, the code is easy to understand, and after this operation the values in the global variable are all in place and ready to work.

How to allocate/reclaim physical memory? The answer is the partner algorithm

Partner algorithm series has said several pieces, here to see the picture to understand what partner algorithm, partner algorithm pays attention to the continuity of physical memory, attention is continuity!

​

For example, to allocate memory space for 4(2^2) pages (16K), the algorithm first checks whether the free list is empty from free_areA2. If there are free blocks, the algorithm allocates the free list from free_area3. If there are no free blocks, the algorithm allocates 16K from free_area3 (32K blocks). Add the extra memory (16K) to free_areA2. If free_areA3 is also not free, then the space is allocated from the next level up to free_area max_order. If there is no space at the top level, then the allocation fails.

Free is the reverse of the application process. When a memory block is freed, it is first checked in the free_area linked list to see if there is any partner block. If there is no partner block, it is directly inserted into the head of the linked list. If there are or blocks, it is removed from the list and merged into a large block, and then it continues to find if the combined block has a partner in the larger list until it cannot be merged or has been merged to the maximum block 2^max_order.

As those of you who have read this series of articles have probably noticed, I like to use stories and metaphors to illustrate how the kernel works. For better understanding, I also think that the companion algorithm is very much like the algorithm that sells standard pork cubes.

Physical memory is a whole pig, has been cut into 1 catty 1 catty, but also connected together, each catty are posted a label, and the boss only press 1 catty (2^0), 2 catty (2^1), 4 catty (2^2),… 256 kg (2^8) way to sell. The counter was divided into nine groups

Zhang SAN came to 7 jin of pork, how to do? ** If zhang SAN returns it, check if there is any serial number that can be connected together in the existing 8 jin group. If there is, two 8 jin groups can be combined into 16 jin and put into the 16 jin group. If you don’t have the 8 kg of pork, you will hang it in group 2 (2^3) in the picture above and sell it again.

Do you have a picture in your head? So the question is, why does it sell pork like this, and what are the benefits? Simple: At least two benefits:

First: sell meat fast, high efficiency, standardized things the best to sell.

Second: to prevent too much broken meat, the back of the people want to buy a large piece of pork to buy. Think about it. Is that true? If you cut as much as you want every time a customer comes in, will you still be able to buy 10 jin of pork together after running for a while? Probably a packet of minced meat, with even a couple of edges in it, and the result of minced meat is cumbersome and inefficient. If the result of the buddy algorithm is that after running for a period of time, the 0, 1 and 2 groups in the figure have saleable pork ah, Brother Zhang returned the 8 jin (in fact, he pointed to 7 jin) of pork, wang five brothers came to 6 jin, directly return brother Zhang to Wang Five on the line. Extremely efficient.

There are always two sides to everything. What is the disadvantage of it? Simple: at least two disadvantages:

First: waste! There are other ways to solve the problem of waste, but not at this level, but by the slab dispenser, and I don’t want to focus on how the slab dispenser solves this problem.

Second: the merger requirement is so strict that it must be a partner (continuous) to merge into a larger block. This also makes it difficult to have large continuous pork pieces over time.

For example, how to achieve the hongmeng kernel meat algorithm? Please look at the code

LosVmPage *OsVmPhysPagesAlloc(struct VmPhysSeg * seg,size_t nPages)
{
    struct VmFreeList *list = NULL;
    LosVmPage *page = NULL;
    UINT32 order;
    UINT32 newOrder;

    if ((seg == NULL) || (nPages == 0)) {
        return NULL;
    }
 // Because the partner algorithm allocation unit is 1, 2, 4, 8 pages, such as nPages = 3, it needs to be divided from free list 4, and the remaining 1 page needs to be split into free list 1
    order = OsVmPagesToOrder(nPages);// Calculate which block group to use according to the page number
    if (order < VM_LIST_ORDER_MAX) {// Order cannot be greater than 9 :256*4K = 1M
        for (newOrder = order; newOrder < VM_LIST_ORDER_MAX; newOrder++) {// If no, look for a bigger one
            list = &seg->freeList[newOrder];// Start with the most suitable block
            if (LOS_ListEmpty(&list->node)) {// If the list is empty, it is not found
                continue;// Continue to look for larger pieces
            }
            page = LOS_DL_LIST_ENTRY(LOS_DL_LIST_FIRST(&list->node)， LosVmPage， node);// Find the first node, because the list is the same size of the physical page frame
            gotoDONE; }}return NULL;
DONE:
    OsVmPhysFreeListDelUnsafe(page);// Remove the physical page box from the list
    OsVmPhysPagesSpiltUnsafe(page， order， newOrder);// Split the physical page frame and attach the pages that do not need to the corresponding free linked list
    return page;
}

/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * this function is very much like to sell pork, cut a large piece of meat, -leonard: well, let's put the leftovers back in the oldOrder. -leonard: I wanted 2^2 meat, but I found a 2^8 meat * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
STATIC VOID OsVmPhysPagesSpiltUnsafe(LosVmPage *page， UINT8 oldOrder， UINT8 newOrder)
{
    UINT32 order;
    LosVmPage *buddyPage = NULL;

    for (order = newOrder; order > oldOrder;) {// the meat mincing process is to cut the excess meat into 2^ 7,2 ^6... Standard block,
        order--;// Cut smaller pieces and hang them one by one on the corresponding free list
        buddyPage = &page[VM_ORDER_TO_PAGES(order)];//@note_good cut off the excess meat first. Because LosVmPage itself is on a large array, page[nPages] can be located directly
        LOS_ASSERT(buddyPage->order == VM_LIST_ORDER_MAX);// The order of the physical page box not attached to the corresponding block free linked list of the partner algorithm must be VM_LIST_ORDER_MAX
        OsVmPhysFreeListAddUnsafe(buddyPage， order);// Attach the split node to the list with the corresponding serial number, buddyPage->order = order}}Copy the code

For the convenience of understanding the details of the code, here said a situation: for example, the third brother to buy 3 catties, found that 4 catties, 8 catties are not available, only 16 catties how to do? Not 16 pounds, but 4 pounds. At this time, it is necessary to split the meat into 8, 4, 4, of which 4 catties are given to Zhang SAN Ge, and the remaining 8 catties, 4 catties, are hung on the corresponding chain list. OsVmPhysPagesSpiltUnsafe is doing the work of splitting pork.

How does the partner algorithm initialize the linked list

// Initializes the free linked list and allocates physical page frames using the buddy algorithm
STATIC INLINE VOID OsVmPhysFreeListInit(struct VmPhysSeg *seg)
{
    int i;
    UINT32 intSave;
    struct VmFreeList *list = NULL;

    LOS_SpinInit(&seg->freeListLock);// Initializes the spin lock used for allocation

    LOS_SpinLockSave(& seg - > freeListLock, & intSave);for (i = 0; i < VM_LIST_ORDER_MAX; i++) {// Iterate over the partner algorithm's free block group list
        list = &seg->freeList[i]; // One by one
        LOS_ListInit(&list->node); // losvmpage. node will hang to list->node
        list->listCnt = 0;   // The number on the list defaults to 0
    }
    LOS_SpinUnlockRestore(& seg - > freeListLock intSave); }Copy the code

Hongmeng is for the future design of the system, forward-looking, far-reaching pattern, sophisticated design, massive knowledge points, the kernel source code with Chinese annotations for more than three months, the more in-depth intensive reading of the kernel source code, the more can feel the designer’s delicate intentions, innovative breakthroughs, to pay tribute to the developers. It is no exaggeration to say that hongmeng kernel source code can be used as a university C language, data structure, operating system, assembly language four courses of teaching projects. Such a treasure, not to further research is a waste of goods, can not bear.

Intensive reading of the kernel source code

Four code stores synchronous annotation kernel source code, >> view the Gitee repository

Analysis of 100 blogs. Dig deep into the core

Add comments to hongmeng kernel source code process, sort out the following article. Content based on the source code, often in life scene analogy as much as possible into the kernel knowledge of a scene, with a pictorial sense, easy to understand memory. It’s important to speak in a way that others can understand! The 100 blogs are by no means a bunch of ridiculously difficult concepts being put forward by Baidu. That’s not interesting. More hope to make the kernel become lifelike, feel more intimate. It’s hard, it’s hard, but there’s no turning back. 😛 and code bugs need to be constantly debug, there will be many mistakes and omissions in the article and annotation content, please forgive, but will be repeatedly amended, continuous update. Xx represents the number of modifications, refined, concise and comprehensive, and strive to create high-quality content.

Compile build The fundamental tools Loading operation Process management
Compile environment

The build process

Environment script

Build tools

Designed.the gn application

Ninja ninja

 Two-way linked list

Bitmap management

In the stack way

The timer

Atomic operation

Time management

 The ELF format

The ELF parsing

Static link

relocation

Process image

 Process management

Process concept

Fork

Special process

Process recycling

Signal production

Signal consumption

Shell editor

Shell parsing
Process of communication Memory management Ins and outs Task management
spinlocks

The mutex

Process of communication

A semaphore

Incident control

The message queue

 Memory allocation

Memory management

Memory assembly

The memory mapping

Rules of memory

Physical memory

 Total directory

Scheduling the story

Main memory slave

The source code comments

Source structure

Static site

 The clock task

Task scheduling

Task management

The scheduling queue

Scheduling mechanism

Thread concept

Concurrent parallel

The system calls

Task switching
The file system Hardware architecture
File concept

The file system

The index node

Mount the directory

Root file system

Character device

VFS

File handle

Pipeline file

 Compilation basis

Assembly and the cords

Working mode

register

Anomaly over

Assembly summary

Interrupt switch

Interrupt concept

Interrupt management

HongMeng station | into a little bit every day, the original is not easy, welcome to reprint, please indicate the source.