UCORE lab2 physical memory management experiment report

After experiment 1, we made a system that can be started , Experiment 2 mainly involves the physical memory management of the operating system . The operating system in order to use memory , You also need to efficiently manage memory resources . In Experiment 2, you will understand and complete a simple physical memory management system by yourself .、

The experiment purpose

• Understand the translation mechanism based on segment page memory address
• Understand the establishment and use of page table
• Understand how to manage physical memory

Experimental content

This experiment consists of three parts . First, learn how to discover the physical memory in the system ; Then learn how to establish a preliminary management of physical memory , That is, understanding continuous physical memory management ; Finally, understand the operation related to page table , That is, how to establish a page table to realize the mapping between virtual memory and physical memory , Have a comprehensive understanding of segment page memory management mechanism . The memory management implemented in this experiment is still very basic , It doesn't involve the optimization of the actual machine , For example cache Optimization, etc . If you have spare time , Try to complete the extension exercise .

practice

practice 0： Fill in the existing experiment

This experiment relies on experiments 1. Please take your experiment 1 Fill in the code in this experiment. There are “LAB1” The corresponding part of the notes . Tips ： May adopt diff and patch Tool for semi-automatic merging （merge）, Some graphical comparisons can also be used /merge Tools to manually merge , such as meld,eclipse Medium diff/merge Tools ,understand Medium diff/merge Tools etc. .

Pictured , open meld Software

And then lab1 and lab2 Compare the contents of

The result of the comparison is

Among them * Document marked with , That is, different files , Copy it
To lab2 that will do . The final will be kern/debug/kdebug.ckern/init/init.c kern/trap/trap.c Three files copied to lab2 In the folder , Finish the exercise 0.

practice 1： Realization first-fit Continuous physical memory allocation algorithm （ You need to program ）

In the realization of first fit The memory allocation algorithm's recycle function , Consider merging between free blocks with consecutive addresses . Tips : When creating a linked list of free page blocks , You need to sort by the starting address of the free page block , Form an orderly linked list . It may change default_pmm.c Medium default_init,default_init_memmap,default_alloc_pages, default_free_pages And so on . Please check carefully and understand default_pmm.c The comments in .

Please briefly describe your design and implementation process in the experimental report . Please answer the following questions ：

• Yours first fit Whether there is room for further improvement

Prepare knowledge ：

First-Fit( First adaptation algorithm )：
The first adaptation algorithm searches the idle partition table from the first table entry , Assign the first available free space to the job , The purpose of this method is to reduce the search time . The algorithm tends to take advantage of the idle partition in the low address part of memory , Thus, the large free area of the high address part is reserved , This creates conditions for large jobs that arrive later to allocate large memory space . The disadvantage is that it will cause external debris

assert() function ：
assert The function of is to evaluate the expression first expression , If the value is false （ That is to say 0）, Then it goes first to stderr Print an error message , And then by calling abort To stop the program running .

list.h in

struct list_entry {
    
 struct list_entry *prev, *next;// Two pointers , Parent child nodes 
};
typedef struct list_entry list_entry_t;// Rename it to list_entry_t
list_init Initialize a new one list_entry
list_add , list_add_before and list_add_after  Is to add a new entry 
list_del Is to delete an entry from the list 
list_del_init Is to delete from the list ─ Entries and redefine it 
list_empty Is to judge whether the list is empty 
list_next and list_prev Get the previous item and the latter item of the list respectively 
le2page The definition of ：
 //  Convert list to page 
#define le2page(le, member)
 to_struct((le), struct Page, member)

Physical page data structure Page

struct Page {
    
 int ref;
 //ref It means , This page is counted by the reference of the page table , That is, the number of virtual pages mapped to this physical page . If this page is referenced by the page table , That is, a page table item in a page table sets a virtual page to this Page Manage the mapping relationship of physical pages , It will Page Of ref Add one ; conversely , If the page entry is cancelled , That is, the mapping relationship is released , It will Page Of ref Minus one .
 uint32_t flags;
 //flags Indicates the status flag of this physical page , There are two flag bit states , by 1 When , This page stands for free state , Can be assigned , But you can't release it ; If 0, Then it means that this page has been allocated , Can't be assigned , But it can be released .
 unsigned int property;
 //property Used to record the number of consecutive free pages , Note that this member is used 
 This of the variable Page It must be the starting address of a contiguous memory block （ The address on the first page ）.
 list_entry_t page_link;
 //page_link It is a bi-directional linked list pointer convenient for linking multiple free blocks of continuous memory , Continuous memory free blocks utilize the member variables of this page page_link To link other contiguous memory free blocks smaller and larger than its address , When releasing, just put the space back into the two-way linked list through the pointer .
};

Modify the function ：

default_pmm.c It is almost implemented in the code first-fit Algorithm , But there is still a problem , So that it can't pass the inspection . because first-fit The algorithm requires that the free memory blocks be connected from small to large according to the address . But the ready-made code has not yet achieved this , So we need to manually modify the relevant code .

First of all to see default_init function ：

// initialization free_area
static void
default_init(void) {
    
 list_init(&free_list); // The list has only one header pointer 
 nr_free = 0; // The number of free pages is set to 0
}

First of all, the macro is defined ：

free_area_t free_area;
#define free_list (free_area.free_list) // Maintain all free memory blocks , It's a two-way list , At the beginning, it's prev and next All point to themselves .
#define nr_free (free_area.nr_free) // Number of free pages 

the free_area.free_list( Global free linked list entry ) Defined as free_list, take free_area.nr_free( Number of global free pages ) Defined as nr_free.

stay default_init in , First the free_list Conduct init initialization , Then set the number of free pages to 0( Because I haven't started counting the number of free pages , So it is 0).

Next look at default_init_memmap function

// initialization n A free page linked list and block Add to free_list in .
static void
default_init_memmap(struct Page *base, size_t n) {
    
 assert(n > 0); // Use assert macro , Abort the program when false 
 struct Page *p = base; // Make a statement base Page of , Then generate the starting address 
 by base Of n Consecutive pages 
 for (; p != base + n; p ++) {
     // initialization n Block physical pages 
 assert(PageReserved(p)); // Check whether it is a reserved page , If it is , initialization 
 p->flags = p->property = 0; // Set up markers ,flag by 0 Indicates that you can assign 
 //property by 0 Indicates that continuous blank pages are 0
 set_page_ref(p, 0); // The number of virtual pages mapped to this physical page is set to 0
 }
 base->property = n;// The first page table is base Of property Set to n, Because there is n A free block 
 SetPageProperty(base);// Set flag bit 
 nr_free += n; // Set the number of free pages to n
 //list_add(&free_list, &(base->page_link));  Before the change 
 // Subsequent continuous empty pages should be set as reserved pages and then linked into a two-way linked list .
 list_add_before(&free_list, &(base->page_link));// After modification 
}

This function is passed in base The address of the page and the number of physical pages generated n, Then initialize the physical page and set it as reserved page and base Page connection . And will modify base page property by n, modify nr_free by n, Record the number of free pages .

Allocate a specified number of free page Code for , namely

default_alloc_pages function ：

// Because it is first-fit function , So allocate the first continuous memory that can be used for allocation 
static struct Page * default_alloc_pages(size_t n) {
    //n Indicates the size of the page to be allocated 
 assert(n > 0); //n The value of should be greater than 0
 // If n>nf_free, It means that such a large amount of memory cannot be allocated , return NULL that will do 
 if (n > nr_free)
  {
    
 return NULL;
 }
 // Explain enough to allocate , So find it 
 struct Page *page = NULL;
 list_entry_t *le = &free_list;// Declare the header of the free linked list 
 //  lookup n Or more free page blocks , If you find , Then judge whether it is greater than n, Greater than n Then split it 
 //  And add the remaining free page blocks after splitting back to the linked list 
 while ((le = list_next(le)) != &free_list)
 //  If list_next(le)) == &free_list It indicates that the whole bidirectional linked list has been traversed 
 {
    
 //  here le2page Will be le The address of -page_link  stay Page The migration , To find  Page  The address of 
 struct Page *p = le2page(le, page_link);
 // It shows that you have found a continuous free memory that can be satisfied , Give Way page be equal to p that will do , Exit loop 
 if (p->property >= n) // Find the page 
 {
    
 page = p;
 break;
 }
 }
 if (page != NULL)
 {
    
 // If property>n Words , We need to add the extra memory to the linked list 
 if (page->property > n)
 {
    
 // Create a new Page, The starting address is page+n
 struct Page *p = page + n;
 p->property = page->property - n;
 // Put it property Set to page->property-n
 SetPageProperty(p);
 //  Insert the extra after the allocated page block 
 list_add(&(page->page_link), &(p->page_link));
 }
 //  Delete the allocated free page in the free page list 
 list_del(&(page->page_link));
 // Because of the allocation of n Memory , so nr_free-n that will do 
 nr_free -= n;
 ClearPageProperty(page);
 }
  // Returns the allocated memory 
 return page;
}

This function is used to allocate free pages , According to the notes , First judge p->property Size , If it is >=n, Then make some modifications to the flag bit , If it is >n, Then you need to split the page block and operate , If none of them match, return NULL sign out .( Write step by step according to the notes , The notes are very detailed .)

Available from above , The idea of allocating memory by the operating system is ：

Free memory code , namely default_free_pages function

// release n Page blocks , After the release, we should also consider whether the released block is next to the existing free block , That is, those that can be merged 
// If you can merge , Then merge , Otherwise, directly join the two-way linked list 
static void default_free_pages(struct Page *base, size_t n)
{
    
 assert(n > 0); //n Must be greater than 0
 struct Page *p = base;
 // First of all, will base-->base+n Between the memory tags as well ref initialization 
 for (; p != base + n; p ++)
 {
    
 assert(!PageReserved(p) && !PageProperty(p));
 // take flags and ref Set to 0
 p->flags = 0;
 set_page_ref(p, 0);
 }
 // After the release, put this piece of property Change it to n
 base->property = n;
 SetPageProperty(base);
 list_entry_t *le = list_next(&free_list);
 //  Check whether it can be merged into the appropriate page block 
 while (le != &free_list)
 {
    
 p = le2page(le, page_link);
 le = list_next(le);
 // If this block is in front of the next free block , The two can be combined 
 if (base + base->property == p)
 {
    
 // Give Way base Of property Equal to the sum of the sizes of the two blocks 
 base->property += p->property;
 // Delete another free block 
 ClearPageProperty(p);
 list_del(&(p->page_link));
 }
 // If this block is after the last free block , The two can be combined 
 else if (p + p->property == base)
 {
    
 // take p Of property Set to the sum of the two 
 p->property += base->property;
  // Delete the following free blocks 
 ClearPageProperty(base);
 base = p;
 // Note that you need to p Delete , Because then confirm the insertion position again 
 list_del(&(p->page_link));
 }
 }
 // The overall free space has increased n
 nr_free += n;
 le = list_next(&free_list);
 //  Add the merged appropriate page blocks back to the empty page block linked list 
 // Because you need to arrange the list in the order of memory from small to large , Therefore, it is necessary to find the position that should be inserted 
 while (le != &free_list)
 {
    
 p = le2page(le, page_link);
 // Find the right place ：
 if (base + base->property <= p)
 {
    
 break;
 }
 // Otherwise, the linked list items are backward , Continue to find 
 le = list_next(le);
 }
 // take base Insert it into the correct position just found 
 list_add_before(le, &(base->page_link));
}

This function is used to add the released page back to the page list , The practice in this experiment is to traverse the linked list , Find the address of the first page that is greater than the address of the first page released , First, judge whether the base address of the released page plus the number of released pages is just equal to the found address , If yes, merge , Similarly, find the first one before this page property Not for 0 Page of , Judge whether the released page and the previous page are continuous , If continuous, merge .

The idea of freeing memory ：

After completing the related functions , Conduct make qemu Instructions , You can see ：

You can see , Memory allocated successfully , The algorithm passed the test .

Question answering

• Yours first fit Whether there is room for further improvement

First of all, we know that the complexity of the algorithm in allocating and releasing memory is O(n), Because you need to access the linked list , Therefore, the complexity is inevitably O(n);

We can use binary search tree to manage memory . Binary search tree is mainly used to sort addresses , Put into use free Time can be in O(logn) Complete the search of the location of the linked list items in time , So as to realize the optimization of time . As follows ：

Sort by address , That is to ensure that the address value of the left node of any node of the binary tree is less than its own address value , The address value of the right node is greater than its own address value , Optimize by this method , We can do that O(n) The complexity of memory allocation , But it can. O(logn) The complexity of memory release , Because the process of judging the merger has been optimized . ad locum , We are right. LEN No requirements , But you have to make sure that X0<X1<X2<X3<X4<X5<X6, And there is no intersection and no adjacency between addresses . Through this method, the complexity of the algorithm is optimized .

practice 2： Find the page table item corresponding to the virtual address （ You need to program ）

By setting the page table and the corresponding page table item , The corresponding relationship between virtual memory address and physical memory address can be established . Among them get_pte Function is an important step in setting page table items . This function finds the kernel virtual address of the secondary page table entry corresponding to a virtual address , If this secondary page entry does not exist , Then a secondary page table containing this item is allocated . This exercise needs to be completed get_pte function in kern/mm/pmm.c, Realize its function . Please check carefully and understand get_pte Comments in functions .get_pte The function call diagram is as follows ：

Please briefly describe your design and implementation process in the experimental report . Please answer the following questions ：

• Please describe the page directory entry （Page Directory Entry） And page table entries （Page Table Entry） The meaning of each component of the and its impact on ucore The potential use of .
• If ucore Accessing memory during execution , Page access exception occurred , What does the hardware do ？

Prepare knowledge ：

x86 The architecture divides memory addresses into three types ： Logical address （ Also called virtual
Address ）、 Linear address and Physical address .

• The logical address is the address used in the program instruction .
• The physical address is the address where the memory is actually accessed .
• Logical address can get linear address through the address mapping of segment management , Linear address through page Manage the address mapping to get the physical address .

get_pte The function gives the linear address , namely linear address. The relationship between the three is ： Linear address （Linear Address） Is the middle layer between the logical address and the physical address transformation . The program code generates a logical address , Or the offset address in the segment , Add the base address of the corresponding segment to generate a linear address . If paging is enabled , Then the linear address can be transformed to produce a physical address .

The address conversion is shown in the figure ：

Ucore The page management of is realized through a two-level page table . The first level page table is stored in high 10 In a , The secondary page table is stored in the middle 10 In a , final 12 Bit represents offset , It can be proved that , Page size is 4KB（2 Of 12 Power ,4096）.

• Directory It is a first level page table
• PDX(la) Can get Directory( Get the first level page table )
• Table It is a secondary page table
• PTX(la) Can get Table( Get the secondary page table )

get_pte Some macros and definitions are given in the comments of ：

• PDX(la)： Return the virtual address la Page directory index of
• KADDR(pa): Return the physical address pa Corresponding virtual address
• set_page_ref(page,1): Set this page to be referenced once
• page2pa(page): obtain page The physical address of the page managed
• struct Page * alloc_page() : Assign a page
• memset(void * s, char c, size_t n) : Set up s Point to the front of the address n Bytes to ‘c’
• PTE_P 0x001 Indicates that the physical memory page exists
• PTE_W 0x002 Indicates that the contents of the physical memory page are writable
• PTE_U 0x004 Indicates that the physical memory page content of the corresponding address can be read

The code is as follows ：

// This function finds the kernel virtual address of the secondary page table entry corresponding to a virtual address , If this secondary page entry does not exist , Then a secondary page table containing this item is allocated 
// pgdir:PDT Kernel virtual address  la： Need mapped linear address  creat： Decide whether to PT Assign the logical value of the page 
//return vaule: This pte Kernel virtual address 
pte_t *get_pte(pde_t *pgdir, uintptr_t la, bool create)
{
    
 // Find the first level page table PDE
 pde_t *pdep = pgdir + PDX(la);
 // If it exists , Return the corresponding PTE that will do 
 if (*pdep & PTE_P) {
    
 pte_t *ptep = (pte_t *)KADDR(*pdep & ~0x0fff) + PTX(la);
 return ptep;
 }
 // If it doesn't exist, assign it page
 struct Page *page;
 if (!create || ((page = alloc_page()) == NULL))
 {
    
 return NULL;
 }
 // To find the table on this page , The number of citations +1
 set_page_ref(page, 1);
 // obtain page The linear address of 
 uintptr_t pa = page2pa(page) & ~0x0fff;
 // Convert to virtual address and initialize to 0, Because the mapping has not yet started 
 memset((void *)KADDR(pa), 0, PGSIZE);
  // Set control bit , Simultaneous setting PTE_U,PTE_W and PTE_P, The software representing the user status can read the physical memory page content of the corresponding address 、 The contents of the physical memory page can be written 、 Physical memory page exists .
 *pdep = pa | PTE_P | PTE_W | PTE_U;
 // return PTE
 pte_t *ptep = (pte_t *)KADDR(pa) + PTX(la);
 // Return the address of the corresponding page item 
 return ptep;
}

What to pay attention to ：
adopt default_alloc_pages() The address of the assigned page is not the address of the real page , Actually, it's just Page The address of this structure , Therefore, it is necessary to use page2pa() take Page The address of this structure is converted into the linear address of the real physical page address , It should be noted that ： Whether it's * or memset All of them operate on virtual addresses, so it is necessary to convert the real physical page address into the kernel virtual address .

Question answering ：

• Please describe the page directory entry （Page Directory Entry） And page table entries （Page Table Entry） The meaning of each component of the and its impact on ucore The potential use of .

Page catalog entry （Page Directory Entry） Composition and pair ucore
The potential role of ：


Page table item （Page Table Entry） The composition of ucore In terms of the
Potential effects ：


To make a long story short , Page directory entries are first level page tables , The starting address of each secondary page table is stored , Page table is a secondary page table , The starting address of each page is stored . A virtual address （ Linear address ） The final physical address is translated through the page mechanism .

The main function of page table is ： If in the system , Physical memory and virtual memory are one-to-one correspondence , Then there will be many page tables in the process space , At the same time, it will occupy a lot of space , that , In order to solve this problem, multi-level page tables appear .

• If ucore Accessing memory during execution , Page access exception occurred , What does the hardware do ？

1. The hardware is stuck in the kernel , Save program counters on the stack . Most machines store various status information of the current instruction in a special file CPU In the register .
2. Start an assembly code routine to store general-purpose registers and other volatile information , To avoid being damaged by the operating system . This routine calls the operating system as a function .
3. When the operating system finds a missing page interrupt , Try to find out which virtual page you need . Usually a hardware register contains this information , If not , The operating system must retrieve program counters , Take out this instruction , Analyze this instruction with software , See what it's doing when the page breaks .
4. Once you know the virtual address where the missing page interrupt occurs , The operating system checks whether this address is valid , And check whether the access and protection are consistent . If it's not consistent , Send a signal to a process or kill it . If the address is valid and there is no protection, an error occurs , The system checks whether there is a free page box . If there is no free page box , Execute the page replacement algorithm to find a page to eliminate .
5. If the selected page box “ dirty ” 了 , Schedule the page to be written back to disk , And a context switch occurs , Suspend the process that caused the missing page interrupt , Let other processes run until the disk transfer is over . in any case , The page box is marked as busy , To avoid being occupied by other processes for other reasons .
6. Once the page box “ clean ” after （ Either immediately or after writing back to disk ）, The operating system finds the address of the required page on disk , Mount it through disk operation . After the page is loaded , The process that caused the missing page interrupt is still suspended , And if there are other runnable user processes , Select another user process to run .
7. When a disk interrupt occurs , Indicates that the page has been loaded , The page table has been updated to reflect its location , The page box is also marked as normal .
8. Restore the state before the page break instruction occurs , The program counter points back to this instruction .
9. Schedule the process that caused the missing page interrupt , The operating system returns the assembly language routine that calls it .
10. This routine restores registers and other status information

practice 3： Release the page where a virtual address is located and unmap the corresponding secondary page table entry （ You need to program ）

When a physical memory page containing a virtual address is released , You need to make the management data structure corresponding to this physical memory page Page Do relevant cleaning treatment , Make this physical memory page free ; In addition, the secondary page table entries representing the corresponding relationship between virtual address and physical address need to be cleared . Please check carefully and understand page_remove_pte Comments in functions . So , It needs to be completed in kern/mm/pmm.c Medium page_remove_pte function .page_remove_pte The function call diagram is as follows ：

Please briefly describe your design and implementation process in the experimental report . Please answer the following questions ：

• data structure Page Global variable of （ It's actually an array ） Whether each item of the page table corresponds to the page directory item and page table item in the page table ？ If there is , What is the corresponding relationship ？
• If you want the virtual address to be equal to the physical address , How to modify lab2, Finish this ？ Encourage programming to accomplish this problem

Ideas ： Check whether the page table entry exists , If there is , Map its corresponding
The shooting relationship is cancelled , And will PTE eliminate , Then refresh tlb that will do .

static inline void
page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep)
{
    
 // Check page directory Whether there is 
 // Exercise 2 we have learned  PTE_P Used to represent page dir Whether there is 
 if (*ptep & PTE_P)
 {
    
 struct Page *page = pte2page(*ptep);
 // (page_ref_dec(page) take page Of ref reduce 1, And return to minus 1 After that ref
 if (page_ref_dec(page) == 0) // If ref by 0, be free that will do 
 {
    
 free_page(page);
 }
 // Clear the second page table  PTE
 *ptep = 0;
  // Refresh  tlb, Remove the secondary page table that clears the relationship , Update page directory entry 
 tlb_invalidate(pgdir, la);
 }
}

After writing the code , It can be executed make qemu, Test exercise two and
Is the code of exercise 3 correct , The operation results are as follows ：

[email protected]:~/os_kernel_lab/labcodes/lab2$ make qemu
+ cc kern/mm/pmm.c
kern/mm/pmm.c:266:1: warning: ‘boot_alloc_page’ defined but not
used [-Wunused-function]
 boot_alloc_page(void) {
    
 ^~~~~~~~~~~~~~~
+ ld bin/kernel
+ ld bin/kernel_nopage
 Recorded 10000+0  Read in of 
 Recorded 10000+0  Write 
5120000 bytes (5.1 MB, 4.9 MiB) copied, 0.0208672 s, 245 MB/s
 Recorded 1+0  Read in of 
 Recorded 1+0  Write 
512 bytes copied, 0.000204289 s, 2.5 MB/s
 Recorded 265+1  Read in of 
 Recorded 265+1  Write 
135832 bytes (136 kB, 133 KiB) copied, 0.000493457 s, 275 MB/s
WARNING: Image format was not specified for 'bin/ucore.img' and
probing guessed raw.
 Automatically detecting the format is dangerous for raw
images, write operations on block 0 will be restricted.
 Specify the 'raw' format explicitly to remove the
restrictions.
(THU.CST) os is loading ...
Special kernel symbols:
 entry 0xc0100036 (phys)
 etext 0xc0106f2e (phys)
 edata 0xc011d000 (phys)
 end 0xc02a4960 (phys)
Kernel executable memory footprint: 1683KB
ebp:0xc0119f38 eip:0xc0100aa9 arg:0x00010094 0x00010094
0xc0119f68 0xc01000cd
 kern/debug/kdebug.c:305: print_stackframe+21
ebp:0xc0119f48 eip:0xc0100d9f arg:0x00000000 0x00000000
0x00000000 0xc0119fb8
 kern/debug/kmonitor.c:129: mon_backtrace+10
ebp:0xc0119f68 eip:0xc01000cd arg:0x00000000 0xc0119f90
0xffff0000 0xc0119f94
 kern/init/init.c:48: grade_backtrace2+33
ebp:0xc0119f88 eip:0xc01000f7 arg:0x00000000 0xffff0000
0xc0119fb4 0x0000002b
 kern/init/init.c:53: grade_backtrace1+38
ebp:0xc0119fa8 eip:0xc0100116 arg:0x00000000 0xc0100036
0xffff0000 0x0000001d
 kern/init/init.c:58: grade_backtrace0+23
ebp:0xc0119fc8 eip:0xc010013c arg:0xc0106f5c 0xc0106f40
0x00187960 0x00000000
 kern/init/init.c:63: grade_backtrace+34
ebp:0xc0119ff8 eip:0xc010008b arg:0xc010713c 0xc0107144
0xc0100d27 0xc0107163
 kern/init/init.c:28: kern_init+84
memory management: default_pmm_manager
e820map:
 memory: 0009fc00, [00000000, 0009fbff], type = 1.
 memory: 00000400, [0009fc00, 0009ffff], type = 2.
 memory: 00010000, [000f0000, 000fffff], type = 2.
 memory: 07ee0000, [00100000, 07fdffff], type = 1.
 memory: 00020000, [07fe0000, 07ffffff], type = 2.
 memory: 00040000, [fffc0000, ffffffff], type = 2.
check_alloc_page() succeeded!
check_pgdir() succeeded!
check_boot_pgdir() succeeded!
-------------------- BEGIN --------------------
PDE(0e0) c0000000-f8000000 38000000 urw
 |-- PTE(38000) c0000000-f8000000 38000000 -rw
PDE(001) fac00000-fb000000 00400000 -rw
 |-- PTE(000e0) faf00000-fafe0000 000e0000 urw
 |-- PTE(00001) fafeb000-fafec000 00001000 -rw
--------------------- END ---------------------
++ setup timer interrupts
0: @ring 0
0: cs = 8
0: ds = 10
0: es = 10
0: ss = 10
+++ switch to user mode +++
100 ticks
100 ticks
100 ticks

By running the results , We can see ucore Show its entry（ Entrance address ）、etext（ The address of the end of the code segment ）、edata（ Address of the end of the data segment ）、 and end（ucore End address ） After the value of , Detect the layout of physical memory in the computer system （e820map What is displayed under ）. Next ucore It can realize a simple memory allocation management with pages as the minimum allocation unit , Complete the establishment of the secondary page table , Enter paging mode , Perform various checks we set up , Finally, it shows ucore The content of the established secondary page table , And respond to clock interrupt in paging mode .

Running at the same time make grade Check the scores

Explain the exercise 2 And practice 3 The codes of are correct .

Question answering

• data structure Page Global variable of （ It's actually an array ） Whether each item of the page table corresponds to the page directory item and page table item in the page table ？ If there is , What is the corresponding relationship ？

pages Each item of the page table corresponds to the page directory item and page table item in the page table ,pages Each item corresponds to the information of a physical page . A page directory item corresponds to a page table , A page table item corresponds to a physical page . Suppose there is N Physics pages ,pages The length of is N, And page directory entries 、 Front of page table item 20 Bit corresponds to the physical page number .

As shown in the figure below ：

One PDE Corresponding 1024 individual PTE, One PTE Corresponding 1024 individual page.

• If you want the virtual address to be equal to the physical address , How to modify
  lab2, Finish this ？ Encourage programming to accomplish this problem

Between physical address and virtual address offset：

phy addr + KERNBASE = virtual addr

therefore ,KERNBASE = 0 when ,phy addr = virtual addr
So the memlayout.h Medium

/* All physical memory mapped at this address */
#define KERNBASE 0x00000000

take KERNBASE Change it to 0 that will do .

Extended exercises Challenge：buddy system（ Buddy system ） Allocation algorithm （ You need to program ）

Buddy System The algorithm divides the available storage space into storage blocks (Block) To manage , The size of each storage block must be 2 Of n The next power (Pow(2, n)), namely 1, 2, 4, 8, 16, 32, 64, 128…

• A minimalist implementation of the reference partner allocator , stay ucore To realize buddy system Allocation algorithm , Sufficient test cases are required to illustrate the correctness of the implementation , Design documentation is required .

Prepare knowledge

buddy system： The essence of partner distribution is a special “ Separation and adaptation ”, About to press memory 2 Divided by the power of , It is equivalent to separating several free linked lists with the same block size , Search the linked list and give the size of the best match with the demand .

The algorithm is basically ：

Allocate memory ：

• Looking for the right size memory block （ Greater than or equal to the required size and closest to 2 The power of , Such as the need to 27, Actual distribution 32）:
  • If you find it , Assigned to the application
  • If not , Separate out the appropriate memory block
    • Separate the free memory blocks larger than the required size in half
    • If it gets to the minimum , Allocate this size .
    • Back to the steps 1( Looking for blocks of the right size )
    • Repeat this step until a suitable block

Free memory ：

• Release the memory block
  • Look for adjacent blocks , See if it's released .
  • If adjacent blocks are also released , Merge these two blocks , Repeat the above steps until Encounter an unreleased adjacent block , Or reach the maximum limit （ That is, all memory It's all released ）.

The whole idea of distributor ：

Monitor and manage memory through a complete binary tree in the form of an array , The node of the binary tree is used to mark the usage status of the corresponding memory block , High level nodes correspond to large blocks , Low level nodes correspond to small blocks , In the allocation and release, we separate and merge blocks through the tag attributes of these nodes . As shown in the figure , Suppose the total size is 16 Unit of memory , We will establish a depth of 5 Full binary tree , The root node subscripts from the array [0] Start , Monitor size 16 The block ; Its left and right child nodes are subscripts [1~ 2], Monitor size 8 The block ; The subscript of the third layer node [3~6] Monitor size 4 The block …… And so on .

Realization buddy system Allocation algorithm

First analysis ucore Implementation process of ：

From practice 1 In the clear , The memory allocation function is in default_pmm.c in
Realized , And in pmm.c Call in , therefore imitation default_pmm.h and
pmm.c The creation is complete buddy.h and buddy.c.

buddy.h The implementation of the ：

#ifndef __KERN_MM_BUDDY_PMM_H__
#define __KERN_MM_BUDDY_PMM_H__
#include <pmm.h>
extern const struct pmm_manager buddy_pmm_manager;
#endif /* ! __KERN_MM_DEFAULT_PMM_H__ */

take pmm.c Medium init_pmm_manager Function pmm_manager
Value is modified to buddy_pmm_manager , namely ：

static void
init_pmm_manager(void) {
    
 pmm_manager = &buddy_pmm_manager;
 cprintf("memory management: %s\n", pmm_manager->name);
 pmm_manager->init();
}

Simultaneous completion buddy.c Code ：

#include <pmm.h>
#include <list.h>
#include <string.h>
#include <default_pmm.h>
#include <buddy.h>
// Some macro definitions from resources 
#define LEFT_LEAF(index) ((index) * 2 + 1)// The value of the left subtree node 
#define RIGHT_LEAF(index) ((index) * 2 + 2)// The value of the right subtree node 
#define PARENT(index) ( ((index) + 1) / 2 - 1)// The value of the parent node 
#define IS_POWER_OF_2(x) (!((x)&((x)-1)))//x Is it right? 2 The power of 
#define MAX(a, b) ((a) > (b) ? (a) : (b))// Judge a,b size 
#define UINT32_SHR_OR(a,n) ((a)|((a)>>(n)))// Move right n position 
#define UINT32_MASK(a)
(UINT32_SHR_OR(UINT32_SHR_OR(UINT32_SHR_OR(UINT32_SHR_OR(UINT32_
SHR_OR(a,1),2),4),8),16))
// Greater than a The smallest of 2^k
#define UINT32_REMAINDER(a) ((a)&(UINT32_MASK(a)>>1))
#define UINT32_ROUND_DOWN(a) (UINT32_REMAINDER(a)?((a)-
UINT32_REMAINDER(a)):(a))// Less than a One of the biggest 2^k
static unsigned fixsize(unsigned size) {
    // Find a memory greater than or equal to the required 2
 Multiple 
 size |= size >> 1;
 size |= size >> 2;
 size |= size >> 4;
 size |= size >> 8;
 size |= size >> 16;
 return size+1;
}
struct buddy2 {
    
 unsigned size;// Indicates the total number of units of managed memory 
 unsigned longest; // Node marking of binary tree , Indicates the free unit of the corresponding memory block 
};
struct buddy2 root[80000];// An array of binary trees , For memory allocation 
free_area_t free_area;
#define free_list (free_area.free_list)
#define nr_free (free_area.nr_free)
struct allocRecord// Record the information of the allocation block 
{
    
 struct Page* base;
 int offset;
 size_t nr;// Block size 
};
struct allocRecord rec[80000];// An array of offsets 
int nr_block;// Number of allocated blocks 
static void buddy_init()
{
    
 list_init(&free_list);
 nr_free=0;
}
// Initialize the node on the binary tree 
void buddy2_new( int size ) {
    
 unsigned node_size;
 int i;
 nr_block=0;
 if (size < 1 || !IS_POWER_OF_2(size))
 return;
 root[0].size = size;
 node_size = size * 2;
 for (i = 0; i < 2 * size - 1; ++i) {
    
 if (IS_POWER_OF_2(i+1))
 node_size /= 2;
 root[i].longest = node_size;
 }
 return;
}
// Initialize the memory mapping relationship 
static void
buddy_init_memmap(struct Page *base, size_t n)
{
    
 assert(n>0);
  struct Page* p=base;
 for(;p!=base + n;p++)
 {
    
 assert(PageReserved(p));
 p->flags = 0;
 p->property = 1;
 set_page_ref(p, 0);
 SetPageProperty(p);
 list_add_before(&free_list,&(p->page_link));
 }
 nr_free += n;
 int allocpages=UINT32_ROUND_DOWN(n);
 buddy2_new(allocpages);
}
// Memory allocation 
int buddy2_alloc(struct buddy2* self, int size) {
    
 unsigned index = 0;// Node label ( The array subscript )
 unsigned node_size;
 unsigned offset = 0;// Offset 
 if (self==NULL)// Can't assign 
 return -1;
 if (size <= 0)// The distribution is unreasonable 
 size = 1;
 else if (!IS_POWER_OF_2(size))// Not for 2 Power time , Take ratio size Bigger 2 Of n
 The next power 
 size = fixsize(size);
 if (self[index].longest < size)// Insufficient allocable memory 
 return -1;
 for(node_size = self->size; node_size != size; node_size /= 2
) {
    
 // Start from the largest root node and look down for the appropriate node 
 // The left subtree takes precedence 
 if (self[LEFT_LEAF(index)].longest >= size)
 {
    
 if(self[RIGHT_LEAF(index)].longest>=size)
 {
    
  index=self[LEFT_LEAF(index)].longest <=
self[RIGHT_LEAF(index)].longest?
LEFT_LEAF(index):RIGHT_LEAF(index);
 // Find the node with smaller memory in the two matching nodes 
 }
 else
 {
    
 index=LEFT_LEAF(index);
 }
 }
 else
 index = RIGHT_LEAF(index);
 }
 self[index].longest = 0;// Mark node as used 
 offset = (index + 1) * node_size - self->size;// Calculate the offset 
 // Refresh up 
 while (index) {
    
 index = PARENT(index);
 self[index].longest =
 MAX(self[LEFT_LEAF(index)].longest,
self[RIGHT_LEAF(index)].longest);
 // Refresh parent node 
 }
 return offset;
}
static struct Page*
buddy_alloc_pages(size_t n){
    
 assert(n>0);
 if(n>nr_free)
 return NULL;
 struct Page* page=NULL;
 struct Page* p;
 list_entry_t *le=&free_list,*len;
 rec[nr_block].offset=buddy2_alloc(root,n);// Record the offset 
 int i;
 for(i=0;i<rec[nr_block].offset+1;i++)
 le=list_next(le);
 page=le2page(le,page_link);
  int allocpages;
 if(!IS_POWER_OF_2(n))
 allocpages=fixsize(n);
 else
 {
    
 allocpages=n;
 }
 // According to the demand n Get the block size 
 rec[nr_block].base=page;// Record allocation block 
 rec[nr_block].nr=allocpages;// Record the number of pages allocated 
 nr_block++;
 for(i=0;i<allocpages;i++)
 {
    
 len=list_next(le);
 p=le2page(le,page_link);
 ClearPageProperty(p);
 le=len;
 }// Change the status of each page 
 nr_free-=allocpages;// Minus the number of pages allocated 
 page->property=n;
 return page;
}
void buddy_free_pages(struct Page* base, size_t n) {
    
 unsigned node_size, index = 0;
 unsigned left_longest, right_longest;
 struct buddy2* self=root;

 list_entry_t *le=list_next(&free_list);
 int i=0;
 for(i=0;i<nr_block;i++)// Find a block 
 {
    
 if(rec[i].base==base)
 break;
 }
 int offset=rec[i].offset;
 int pos=i;// The staging i
 i=0;
 while(i<offset)
 {
    
 le=list_next(le);
  i++;
 }
 int allocpages;
 if(!IS_POWER_OF_2(n))
 allocpages=fixsize(n);
 else
 {
    
 allocpages=n;
 }
 assert(self && offset >= 0 && offset < self->size);// Is it legal 
 node_size = 1;
 index = offset + self->size - 1;
 nr_free+=allocpages;// Update the number of free pages 
 struct Page* p;
 self[index].longest = allocpages;
 for(i=0;i<allocpages;i++)// Recycle allocated pages 
 {
    
 p=le2page(le,page_link);
 p->flags=0;
 p->property=1;
 SetPageProperty(p);
 le=list_next(le);
 }
 while (index) {
    // Merge up , Modify the record value of the ancestor node 
 index = PARENT(index);
 node_size *= 2;
 left_longest = self[LEFT_LEAF(index)].longest;
 right_longest = self[RIGHT_LEAF(index)].longest;

 if (left_longest + right_longest == node_size)
 self[index].longest = node_size;
 else
 self[index].longest = MAX(left_longest, right_longest);
 }
 for(i=pos;i<nr_block-1;i++)// Clear the allocation record this time 
 {
    
 rec[i]=rec[i+1];
 }
 nr_block--;// Update the value of the number of allocated blocks 
}
static size_t
buddy_nr_free_pages(void) {
    
 return nr_free;
}
// Here is a test function 
static void
buddy_check(void) {
    
 struct Page *p0, *A, *B,*C,*D;
 p0 = A = B = C = D =NULL;
 assert((p0 = alloc_page()) != NULL);
 assert((A = alloc_page()) != NULL);
 assert((B = alloc_page()) != NULL);
 assert(p0 != A && p0 != B && A != B);
 assert(page_ref(p0) == 0 && page_ref(A) == 0 && page_ref(B)
== 0);
 free_page(p0);
 free_page(A);
 free_page(B);

 A=alloc_pages(500);
 B=alloc_pages(500);
 cprintf("A %p\n",A);
 cprintf("B %p\n",B);
 free_pages(A,250);
 free_pages(B,500);
 free_pages(A+250,250);

 p0=alloc_pages(1024);
 cprintf("p0 %p\n",p0);
 assert(p0 == A);
 // The following is written based on the sample test in the link 
 A=alloc_pages(70);
 B=alloc_pages(35);
 assert(A+128==B);// Check whether it is adjacent 
 cprintf("A %p\n",A);
 cprintf("B %p\n",B);
  C=alloc_pages(80);
 assert(A+256==C);// Check C Is there any and A overlap 
 cprintf("C %p\n",C);
 free_pages(A,70);// Release A
 cprintf("B %p\n",B);
 D=alloc_pages(60);
 cprintf("D %p\n",D);
 assert(B+64==D);// Check B,D Is it adjacent 
 free_pages(B,35);
 cprintf("D %p\n",D);
 free_pages(D,60);
 cprintf("C %p\n",C);
 free_pages(C,80);
 free_pages(p0,1000);// Release all 
}
const struct pmm_manager buddy_pmm_manager = {
    
 .name = "buddy_pmm_manager",
 .init = buddy_init,
 .init_memmap = buddy_init_memmap,
 .alloc_pages = buddy_alloc_pages,
 .free_pages = buddy_free_pages,
 .nr_free_pages = buddy_nr_free_pages,
 .check = buddy_check,
};

function make qemu, have to

Running normally , And it has been tested to be correct , Can achieve challenge What we need
seek .

Extended exercises Challenge： Memory units of any size slub Allocation algorithm （ You need to program ）

slub Algorithm , Realize efficient memory unit allocation of two-tier architecture , The first layer is memory allocation based on page size , The second layer is to realize memory allocation based on arbitrary size on the basis of the first layer . Can simplify the implementation of , Can reflect its main idea .

• Reference resources linux Of slub Allocation algorithm /, stay ucore To realize slub Allocation algorithm . Sufficient test cases are required to illustrate the correctness of the implementation , Design documentation is required .

Summary of the experiment

The previous exercise 1~3 Let me have a deep understanding of the memory management and other mechanisms of the operating system , For example, different memory allocation algorithms and page tables .

challenge I think it is more challenging , But with practice 1 There is a certain connection , All are to complete the allocation and release of memory . Read the reference link of partner algorithm given in the guide , The author of this article seems to like this algorithm very much , But this algorithm still has some shortcomings , Compared with the practice First-Fit, Instead, its internal fragments have become larger , And it wastes a lot , Such as the need to 9K, Must allocate 16K Space leads to 7K Be wasted . The merger requirements are too strict , Only blocks that meet the partnership can be merged . The advantage is that it can better solve the problem of external fragments , Moreover, it is mentioned in the query of relevant information that the partner algorithm is designed for large memory allocation .

in general ,lab2 The harvest is still great , And as the experimental guide said at the beginning ,lab1 and lab2 More difficult , But through lab1 and lab2 after , Interruption in computer theory 、 Segment page table mechanism 、 The understanding of privilege level will be deeper . It is of great help to the later study .