ucore lab5

UCORE experiment 5

The experiment purpose

Understand the first user process creation process , Implementation mechanism of system call framework ,ucore How to implement system call sys_fork/sys_exec/sys_exit/sys_wait For process management .

Experimental content

experiment 4 Completed the kernel thread , But so far , All operations are executed in kernel mode . experiment 5 The user process... Will be created , Let the user process execute in user mode , And when necessary ucore When supported , You can use system calls to make ucore Provide services . To do this, you need to construct the first user process , And through system call sys_fork/sys_exec/sys_exit/sys_wait To support running different applications , Complete the basic management of the execution process of the user process . See the appendix for the introduction of relevant principles B.

practice 0： Fill in the existing experiment

This experiment relies on experiments 1/2/3/4. Please take your experiment 1/2/3/4 Fill in the code in this experiment. There are “LAB1”/“LAB2”/“LAB3”/“LAB4” The corresponding part of the notes . Be careful ： In order to execute correctly lab5 Test application for , It may be necessary to test the completed experiments 1/2/3/4 Code for further improvements .

stay alloc_proc Function , Add pair proc_struct::wait_state as well as proc_struct::cptr/optr/yptr Initialization of members .
The relationships among processes are as follows ：
parent: proc->parent (proc is children)
children: proc->cptr (proc is parent)
older sibling: proc->optr (proc is younger sibling)
younger sibling: proc->yptr (proc is older sibling)

static struct proc_struct *
alloc_proc(void) {
    struct proc_struct *proc = kmalloc(sizeof(struct proc_struct));
    if (proc != NULL) {
    //LAB4:EXERCISE1 202008010404
    /*
     * below fields in proc_struct need to be initialized
     *       enum proc_state state;                      // Process state
     *       int pid;                                    // Process ID
     *       int runs;                                   // the running times of Proces
     *       uintptr_t kstack;                           // Process kernel stack
     *       volatile bool need_resched;                 // bool value: need to be rescheduled to release CPU?
     *       struct proc_struct *parent;                 // the parent process
     *       struct mm_struct *mm;                       // Process's memory management field
     *       struct context context;                     // Switch here to run process
     *       struct trapframe *tf;                       // Trap frame for current interrupt
     *       uintptr_t cr3;                              // CR3 register: the base addr of Page Directroy Table(PDT)
     *       uint32_t flags;                             // Process flag
     *       char name[PROC_NAME_LEN + 1];               // Process name
     */
    //LAB5 202008010404 : (update LAB4 steps)
    /*
     * below fields(add in LAB5) in proc_struct need to be initialized	
     *       uint32_t wait_state;                        // waiting state
     *       struct proc_struct *cptr, *yptr, *optr;     // relations between processes
     */
        proc->state = PROC_UNINIT;
        proc->pid = -1;
        proc->runs = 0;
        proc->kstack = 0;
        proc->need_resched = 0;
        proc->parent = NULL;
        proc->mm = NULL;
        memset(&(proc->context), 0, sizeof(struct context));
        proc->tf = NULL;
        proc->cr3 = boot_cr3;
        proc->flags = 0;
        memset(proc->name, 0, PROC_NAME_LEN);
        proc->wait_state = 0;
        proc->cptr = proc->optr = proc->yptr = NULL;
    }
    return proc;
}

stay do_fork Function , Add a check on the waiting state of the current process , And the use of set_links Function to set the relationship between processes .

/* do_fork -     parent process for a new child process
 * @clone_flags: used to guide how to clone the child process
 * @stack:       the parent's user stack pointer. if stack==0, It means to fork a kernel thread.
 * @tf:          the trapframe info, which will be copied to child process's proc->tf
 */
int
do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf) {
    int ret = -E_NO_FREE_PROC;
    struct proc_struct *proc;
    if (nr_process >= MAX_PROCESS) {
        goto fork_out;
    }
    ret = -E_NO_MEM;
    //LAB4:EXERCISE2 202008010404
    /*
     * Some Useful MACROs, Functions and DEFINEs, you can use them in below implementation.
     * MACROs or Functions:
     *   alloc_proc:   create a proc struct and init fields (lab4:exercise1)
     *   setup_kstack: alloc pages with size KSTACKPAGE as process kernel stack
     *   copy_mm:      process "proc" duplicate OR share process "current"'s mm according clone_flags
     *                 if clone_flags & CLONE_VM, then "share" ; else "duplicate"
     *   copy_thread:  setup the trapframe on the  process's kernel stack top and
     *                 setup the kernel entry point and stack of process
     *   hash_proc:    add proc into proc hash_list
     *   get_pid:      alloc a unique pid for process
     *   wakeup_proc:  set proc->state = PROC_RUNNABLE
     * VARIABLES:
     *   proc_list:    the process set's list
     *   nr_process:   the number of process set
     */

    //    1. call alloc_proc to allocate a proc_struct
    //    2. call setup_kstack to allocate a kernel stack for child process
    //    3. call copy_mm to dup OR share mm according clone_flag
    //    4. call copy_thread to setup tf & context in proc_struct
    //    5. insert proc_struct into hash_list && proc_list
    //    6. call wakeup_proc to make the new child process RUNNABLE
    //    7. set ret vaule using child proc's pid
    if ((proc = alloc_proc()) == NULL) {
        goto fork_out;
    }
   //LAB5 202008010404 : (update LAB4 steps)
   /* Some Functions
    *    set_links:  set the relation links of process.  ALSO SEE: remove_links:  lean the relation links of process 
    *    -------------------
    *    update step 1: set child proc's parent to current process, make sure current process's wait_state is 0
    *    update step 5: insert proc_struct into hash_list && proc_list, set the relation links of process
    */
    proc->parent = current;
    assert(current->wait_state == 0);// Yes wait_state The inspection of 

    if (setup_kstack(proc) != 0) {
        goto bad_fork_cleanup_proc;
    }
    if (copy_mm(clone_flags, proc) != 0) {
        goto bad_fork_cleanup_kstack;
    }
    copy_thread(proc, stack, tf);

    bool intr_flag;
    local_intr_save(intr_flag);
    {
        proc->pid = get_pid();
        hash_proc(proc);
        set_links(proc);// Set the relationship between processes 

    }
    local_intr_restore(intr_flag);

    wakeup_proc(proc);

    ret = proc->pid;
fork_out:
    return ret;

bad_fork_cleanup_kstack:
    put_kstack(proc);
bad_fork_cleanup_proc:
    kfree(proc);
    goto fork_out;
}

stay idt_init Function , Set interrupt T_SYSCALL The trigger privilege level of is DPL_USER, Make system calls available to user mode processes .

/* idt_init - initialize IDT to each of the entry points in kern/trap/vectors.S */
void
idt_init(void) {
     /* LAB1 202008010404 : STEP 2 */
     /* (1) Where are the entry addrs of each Interrupt Service Routine (ISR)?
      *     All ISR's entry addrs are stored in __vectors. where is uintptr_t __vectors[] ?
      *     __vectors[] is in kern/trap/vector.S which is produced by tools/vector.c
      *     (try "make" command in lab1, then you will find vector.S in kern/trap DIR)
      *     You can use  "extern uintptr_t __vectors[];" to define this extern variable which will be used later.
      * (2) Now you should setup the entries of ISR in Interrupt Description Table (IDT).
      *     Can you see idt[256] in this file? Yes, it's IDT! you can use SETGATE macro to setup each item of IDT
      * (3) After setup the contents of IDT, you will let CPU know where is the IDT by using 'lidt' instruction.
      *     You don't know the meaning of this instruction? just google it! and check the libs/x86.h to know more.
      *     Notice: the argument of lidt is idt_pd. try to find it!
      */
     /* LAB5 202008010404 */ 
     //you should update your lab1 code (just add ONE or TWO lines of code), let user app to use syscall to get the service of ucore
     //so you should setup the syscall interrupt gate in here
    extern uintptr_t __vectors[];
    int i;
    for (i = 0; i < sizeof(idt) / sizeof(struct gatedesc); i ++) {
        SETGATE(idt[i], 0, GD_KTEXT, __vectors[i], DPL_KERNEL);
    }
    SETGATE(idt[T_SYSCALL], 1, GD_KTEXT, __vectors[T_SYSCALL], DPL_USER);// Modified here 
    lidt(&idt_pd);
}

stay trap_dispatch in , Set every 100 After time interruption , The currently executing process is ready to be scheduled . meanwhile , Remove the original "100ticks" Output

static void
trap_dispatch(struct trapframe *tf) {
    char c;

    int ret=0;

    switch (tf->tf_trapno) {
    case T_PGFLT:  //page fault
        if ((ret = pgfault_handler(tf)) != 0) {
            print_trapframe(tf);
            if (current == NULL) {
                panic("handle pgfault failed. ret=%d\n", ret);
            }
            else {
                if (trap_in_kernel(tf)) {
                    panic("handle pgfault failed in kernel mode. ret=%d\n", ret);
                }
                cprintf("killed by kernel.\n");
                panic("handle user mode pgfault failed. ret=%d\n", ret); 
                do_exit(-E_KILLED);
            }
        }
        break;
    case T_SYSCALL:
        syscall();
        break;
    case IRQ_OFFSET + IRQ_TIMER:
#if 0
    LAB3 : If some page replacement algorithm(such as CLOCK PRA) need tick to change the priority of pages,
    then you can add code here. 
#endif
        /* LAB1 202008010404 : STEP 3 */
        /* handle the timer interrupt */
        /* (1) After a timer interrupt, you should record this event using a global variable (increase it), such as ticks in kern/driver/clock.c
         * (2) Every TICK_NUM cycle, you can print some info using a funciton, such as print_ticks().
         * (3) Too Simple? Yes, I think so!
         */
        /* LAB5 202008010404 */
        /* you should upate you lab1 code (just add ONE or TWO lines of code):
         * Every TICK_NUM cycle, you should set current process's current->need_resched = 1
         */
        ticks ++;
        if (ticks % TICK_NUM == 0) {
            assert(current != NULL);
            current->need_resched = 1;
        }
        break;
    case IRQ_OFFSET + IRQ_COM1:
        c = cons_getc();
        cprintf("serial [%03d] %c\n", c, c);
        break;
    case IRQ_OFFSET + IRQ_KBD:
        c = cons_getc();
        cprintf("kbd [%03d] %c\n", c, c);
        break;
    //LAB1 CHALLENGE 1 : YOUR CODE you should modify below codes.
    case T_SWITCH_TOU:
    case T_SWITCH_TOK:
        panic("T_SWITCH_** ??\n");
        break;
    case IRQ_OFFSET + IRQ_IDE1:
    case IRQ_OFFSET + IRQ_IDE2:
        /* do nothing */
        break;
    default:
        print_trapframe(tf);
        if (current != NULL) {
            cprintf("unhandled trap.\n");
            do_exit(-E_KILLED);
        }
        // in kernel, it must be a mistake
        panic("unexpected trap in kernel.\n");

    }
}

practice 1： Load the application and execute （ Need to code ）

do_execv Function call load_icode（ be located kern/process/proc.c in ） To load and parse a in memory ELF Execute file format applications , Set up the corresponding user memory space to place the code segments of the application 、 Data segments, etc , And it should be set proc_struct Member variables in the structure trapframe The content in , Make sure that after executing this process , It can be executed from the starting address set by the application . Set the correct trapframe Content .

Please briefly describe your design and implementation process in the experimental report .

Please describe in the experiment report when you create a user mode process and load the application ,CPU How to make this application finally execute in user mode . That is, the user state process is ucore Select occupancy CPU perform （RUNNING state ） The whole process of implementing the first instruction of the application program .

analysis

perfect load_icode Function code

After determining the execution code and data of the user process , And the virtual space layout of the user process , We are ready to create the user process . In this experiment, the first user process is composed of the second kernel thread initproc Through the hello The application execution code covers initproc User virtual memory space to create , Through a series of calls , Finally through do_execve Function to complete the creation of user processes . The main workflow of this function is as follows ：

① First, prepare to empty the user mode memory space for loading new execution codes . If mm Not for NULL, Set the page table to the kernel space page table , And further judge mm The reference count of minus 1 Is it 0, If 0, It indicates that no process needs the memory space occupied by this process any more , This will be done according to mm Records in , Free the user space memory occupied by the process and the space occupied by the process page table itself . Finally, the current process mm Memory management pointer is null . Because of the initproc It's kernel threads , therefore mm by NULL, The whole process will not be done .

② The next step is to load the application execution code into the newly created user state virtual space of the current process . This involves reading ELF File format , Apply for memory space , Create user state virtual memory space , Loading application execution code, etc .load_icode Function completes the whole complex work .
do_execve function ：

int
do_execve(const char *name, size_t len, unsigned char *binary, size_t size) {
    // Prepare to empty the user mode memory space for loading new execution code 
    struct mm_struct *mm = current->mm;
    if (!user_mem_check(mm, (uintptr_t)name, len, 0)) {
        return -E_INVAL;
    }
    if (len > PROC_NAME_LEN) {
        len = PROC_NAME_LEN;
    }

    char local_name[PROC_NAME_LEN + 1];
    memset(local_name, 0, sizeof(local_name));
    memcpy(local_name, name, len);

    // If mm Not for NULL Deal with it accordingly 
    if (mm != NULL) {
        lcr3(boot_cr3);
        if (mm_count_dec(mm) == 0) {
            exit_mmap(mm);
            put_pgdir(mm);
            mm_destroy(mm);
        }
        current->mm = NULL;
    }

    // Load the application execution code into the newly created user state virtual space of the current process 
    int ret;
    if ((ret = load_icode(binary, size)) != 0) {
        goto execve_exit;
    }
    set_proc_name(current, local_name);
    return 0;

execve_exit:
    do_exit(ret);
    panic("already exit: %e.\n", ret);
}

load_icode The main task of the function is to create a user environment for the user process to run normally . This function has more than a hundred lines , The following important work has been completed ：

① call mm_create Function to apply for the memory management data structure of the process mm Required memory space , Also on mm To initialize ;

② call setup_pgdir To apply for a page size memory space required for a page directory table , And describe ucore Kernel page table of kernel virtual space mapping （boot_pgdir To refer to ） Copy the contents of this new directory table , Finally let mm->pgdir Point to the table of contents on this page , This is the new page directory table of the process , And can correctly map the kernel virtual space ;

③ This code is parsed according to the starting position of the application execution code ELF Format execution program , And call mm_map Functions are based on ELF The format of the execution program describes the various paragraphs （ Code segment 、 Data segment 、BSS Duan et al ） The starting position and size of the corresponding vma structure , And put vma Insert into mm In structure , Thus, it shows the legal user state virtual address space of user process ;

④ Call to allocate physical memory space according to the size of each segment of the executing program , The virtual address is determined according to the starting position of each segment of the execution program , And establish the mapping relationship between physical address and virtual address in the page table , Then copy the contents of each segment of the execution program to the corresponding kernel virtual address , So far, the application execution code and data have been placed in the virtual memory according to the address set at compile time ;

⑤ You need to set the user stack for the user process , Call... For this mm_mmap Function to build the user stack vma structure , Make it clear that the position of the user stack is at the top of the user virtual space , The size is 256 A page , namely 1MB, Allocate a certain amount of physical memory and establish the virtual address of the stack <–> Physical address mapping relationship ;

⑥ thus , In process memory management vma and mm The data structure has been established , So the mm->pgdir Assign values to the cr3 In the register , That is, the virtual memory space of the user process is updated , At this time initproc Has been hello Code and data coverage , Became the first user process , But at this time, the execution site of the user process has not been established ;

⑦ First clear the interrupt frame of the process , Then reset the interrupt frame of the process , Make the interrupt return instruction “iret” after , To be able to make CPU Go to the user state privilege level , And return to the user state memory space , Code snippets using user mode 、 Segments and stacks , And can jump to the first instruction execution of the user process , And ensure that the interrupt can be responded to in the user state ;

We need to set the correct trapframe Content , Make the interrupt return instruction “iret” after , To be able to make CPU Go to the user state privilege level , That is to say 7 Content of step ,load_icode The code of the function part is as follows ：

//(6) setup trapframe for user environment
    struct trapframe *tf = current->tf;
    memset(tf, 0, sizeof(struct trapframe));
    /* LAB5:EXERCISE1 202008010404
     * should set tf_cs,tf_ds,tf_es,tf_ss,tf_esp,tf_eip,tf_eflags
     * NOTICE: If we set trapframe correctly, then the user level process can return to USER MODE from kernel. So
     *          tf_cs should be USER_CS segment (see memlayout.h)
     *          tf_ds=tf_es=tf_ss should be USER_DS segment
     *          tf_esp should be the top addr of user stack (USTACKTOP)
     *          tf_eip should be the entry point of this binary program (elf->e_entry)
     *          tf_eflags should be set to enable computer to produce Interrupt
     */
    tf->tf_cs = USER_CS;
    tf->tf_ds = tf->tf_es = tf->tf_ss = USER_DS;
    tf->tf_esp = USTACKTOP;
    tf->tf_eip = elf->e_entry;
    tf->tf_eflags = FL_IF;
    ret = 0;

According to the notes , We're going to tf_cs Set as segment selector of user status code segment ,tf_ds、tf_es、tf_ss Are set as segment selectors of user status data segments ,tf_esp Set as the top of the user stack ,tf_eip Set to ELF Access to documents e_entry,tf_eflags Enable middle break .

When a user mode process is created and the application is loaded ,CPU How to make this application finally execute in user mode

This question is not only to understand the experiment , It should also be combined with the previous experiment .

① After creating a new user mode process , Kernel thread calls schedule function ,schedule Function in proc_list Find the next in the queue “ be ready ” State user state process , And then call proc_run To run the new process .

② And then proc_run According to the call flow of the previous experiment , eureka kernel_thread_entry. and kernel_thread_entry First the edx Saved input parameters （NULL） Pressing stack , And then through call Instructions , Jump to ebx Function pointed to , namely user_main,user_main Print first userproc Of pid and name Information , And then call kernel_execve.

③kernel_execve Called exec system call , Thus, it goes to the processing routine of the system call . After that, the normal interrupt processing routine , Then control shifted to syscall.c Medium syscall function , Then it is transferred to according to the system call number sys_exec function , Called in this function do_execve Function to complete the loading of the specified application . The calling process is ：vector128 -> __alltraps -> trap -> trap_dispatch -> syscall -> sys_exec -> do_execve.

④ stay do_execve Several settings are made in , Including the page table of the current process , Switch to the kernel PDT, call load_icode Function to initialize the memory space of the entire user thread , Including stack settings and adding ELF Loading of executables , After through current->tf The pointer modifies the current system call trapframe, This enables the user state to be switched when the final interrupt returns , And at the same time, it can correctly transfer control to the entrance of the application .

⑤ At the completion of the do_exec After the function , The process of normal interrupt return , Because the interrupt processing routine is on the stack eip It has been modified to be the entrance of the application , and CS Upper CPL It's user mode , therefore iret When the interrupt returns, the stack will be switched to the user's stack , And complete the privilege level switch , And jump to the entrance of the required application , Start executing the first code of the application .

practice 2: The parent process copies its own memory space to the child process （ Need to code ）

The function that creates the child process do_fork The current process will be copied in execution （ The parent process ） Of the user memory address space to the new process （ Subprocesses ）, Finish copying memory resources . Specifically through copy_range function （ be located kern/mm/pmm.c in ） Realized , Please add copy_range The implementation of the , Ensure that... Can be performed correctly .

Please briefly explain how to design and implement in the experiment report "Copy on Write Mechanism ", Give the outline design , Encourage detailed design .

Copy-on-write（ abbreviation COW） The basic concept of is that if there are multiple users for a resource A（ Such as memory block ） Read it , Then each user only needs to get one pointing to the same resource A The pointer to , You can read the resource . If a user needs to access this resource A Write operation , The system will copy the resource , So that the “ Write operations ” The user gets a copy of the resource A Of “ private ” Copy — resources B, Resources can be B Write operation . The “ Write operations ” Users are interested in resources B Changes to the are invisible to other users , Because other users still see resources A.

analysis

1. Realization copy_range function

do_fork() Complete the copy task , The calling process is ：
do_fork()---->copy_mm()---->dup_mmap()---->copy_range()

copy_range： Process A The contents of the memory in the are copied to the process B in .
Five parameters ：to（ process B The address of the page directory of ）,from（ process A The address of the page directory of ）,share（ sign , To show that is to use dup still share, Here we only use dup（ Copy ） Method , So this parameter is useless here ）,start and end refer to A Start and end of memory space address .

Some useful MACROs or Functions:
page2kva(struct Page *page): return the kernel virtual addr of memory which page managed (SEE pmm.h).
Returns the kernel virtual address of the page managed memory .
page_insert: build the map of phy addr of an Page with the linear addr la.
Create a linear address la And Page Physical address mapping .
memcpy: typical memory copy function.
A typical memory copy function .

int
copy_range(pde_t *to, pde_t *from, uintptr_t start, uintptr_t end, bool share) {
    assert(start % PGSIZE == 0 && end % PGSIZE == 0);
    assert(USER_ACCESS(start, end));
    // copy content by page unit.
    do {
        //call get_pte to find process A's pte according to the addr start, call get_pte The function looks for the starting point of the memory space address A Of PTE
        pte_t *ptep = get_pte(from, start, 0), *nptep;
        if (ptep == NULL) {
            start = ROUNDDOWN(start + PTSIZE, PTSIZE);
            continue ;
        }
        //call get_pte to find process B's pte according to the addr start. If pte is NULL, just alloc a PT, Also look for B Of PTE, If PTE by NULL Assign a PT
        if (*ptep & PTE_P) {
            if ((nptep = get_pte(to, start, 1)) == NULL) {
                return -E_NO_MEM;
            }
        uint32_t perm = (*ptep & PTE_USER);
        //get page from ptep, from ptep Get pages from 
        struct Page *page = pte2page(*ptep);
        // alloc a page for process B, For the process B Assign page 
        struct Page *npage=alloc_page();
        assert(page!=NULL);
        assert(npage!=NULL);
        int ret=0;

        /* LAB5:EXERCISE2 202008010404*/
        // Copy page Content to npage, establish npage Mapping of physical address and linear address of .

        void * kva_src = page2kva(page); // Get source (src) The virtual address where the page is located （ Be careful , At this time PDT Is the page directory table in the kernel state ）
        void * kva_dst = page2kva(npage); // Get the target (dst) The virtual address where the page is located 
        memcpy(kva_dst, kva_src, PGSIZE); // Page data replication 
        ret = page_insert(to, npage, start, perm); // Set the page to the corresponding PTE in 
        
        assert(ret == 0);
        }
        start += PGSIZE;
    } while (start != 0 && start < end);
    return 0;
}

2. Realization "Copy on Write Mechanism "

When a user parent process creates its own child process , The parent process will set its requested user space to read-only , Child processes can share pages in the user memory space occupied by the parent process （ This is a shared resource ）. When any one of these processes modifies a page in this user's memory space ,ucore Will pass page fault The exception learns the operation , And finish copying memory pages , So that both processes have their own memory pages . Changes made by such a process are not visible to another process .

practice 3: Read and analyze the source code , Understand process execution fork/exec/wait/exit The implementation of the , And the implementation of system call （ No coding required ）

Please briefly explain your understanding of fork/exec/wait/exit Analysis of functions . And answer the following questions ：

Please analyze fork/exec/wait/exit How the implementation affects the execution state of the process ？
Please give me ucore Execution state lifecycle diagram of a user state process in （ Package execution status , Execute the transformation relationship between states , And the event or function call that produces the transformation ）.（ Characters can be drawn ）

perform ：make grade. If the displayed application tests all output ok, Is basically correct .（ It uses qemu-1.0.1）

analysis

Yes fork/exec/wait/exit Function and system call analysis

System call name	meaning	The function that completes the service
SYS_exit	process exit	do_exit
SYS_fork	create child process, dup mm	do_fork–>wakeup_proc
SYS_wait	wait child process	do_wait
SYS_exec	after fork, process execute a new program	load a program and refresh the mm
SYS_yield	process flag itself need resecheduling	proc->need_sched=1, then scheduler will rescheule this process
SYS_kill	kill process	do_kill–>proc->flags
SYS_getpid	get the process’s pid

1.do_fork
① Allocate and initialize process control blocks （alloc_proc function ）.
② Allocate and initialize the kernel stack （setup_stack function ）.
③ Check the waiting state of the current process .
④ according to clone_flag Flag copy or share process memory management structure （copy_mm function ）.
⑤ Set the process in the kernel （ In the future, it also includes user mode ） Interrupt frames and execution context required for normal operation and scheduling （copy_thread function ）.
⑥ Put the set process control block into hash_list and proc_list In the linked list of two global processes , And set up set_links.
⑦ Since then , The process is ready to execute , Set the process status to “ be ready ” state .
⑧ Set the return code to that of the child process id Number .

/* do_fork -     parent process for a new child process
 * @clone_flags: used to guide how to clone the child process
 * @stack:       the parent's user stack pointer. if stack==0, It means to fork a kernel thread.
 * @tf:          the trapframe info, which will be copied to child process's proc->tf
 */
int
do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf) {
    int ret = -E_NO_FREE_PROC;
    struct proc_struct *proc;
    if (nr_process >= MAX_PROCESS) {
        goto fork_out;
    }
    ret = -E_NO_MEM;
    //LAB4:EXERCISE2 202008010404
    /*
     * Some Useful MACROs, Functions and DEFINEs, you can use them in below implementation.
     * MACROs or Functions:
     *   alloc_proc:   create a proc struct and init fields (lab4:exercise1)
     *   setup_kstack: alloc pages with size KSTACKPAGE as process kernel stack
     *   copy_mm:      process "proc" duplicate OR share process "current"'s mm according clone_flags
     *                 if clone_flags & CLONE_VM, then "share" ; else "duplicate"
     *   copy_thread:  setup the trapframe on the  process's kernel stack top and
     *                 setup the kernel entry point and stack of process
     *   hash_proc:    add proc into proc hash_list
     *   get_pid:      alloc a unique pid for process
     *   wakeup_proc:  set proc->state = PROC_RUNNABLE
     * VARIABLES:
     *   proc_list:    the process set's list
     *   nr_process:   the number of process set
     */

    //    1. call alloc_proc to allocate a proc_struct
    //    2. call setup_kstack to allocate a kernel stack for child process
    //    3. call copy_mm to dup OR share mm according clone_flag
    //    4. call copy_thread to setup tf & context in proc_struct
    //    5. insert proc_struct into hash_list && proc_list
    //    6. call wakeup_proc to make the new child process RUNNABLE
    //    7. set ret vaule using child proc's pid
    if ((proc = alloc_proc()) == NULL) {
        goto fork_out;
    }
   //LAB5 202008010404 : (update LAB4 steps)
   /* Some Functions
    *    set_links:  set the relation links of process.  ALSO SEE: remove_links:  lean the relation links of process 
    *    -------------------
    *    update step 1: set child proc's parent to current process, make sure current process's wait_state is 0
    *    update step 5: insert proc_struct into hash_list && proc_list, set the relation links of process
    */
    proc->parent = current;
    assert(current->wait_state == 0);

    if (setup_kstack(proc) != 0) {
        goto bad_fork_cleanup_proc;
    }
    if (copy_mm(clone_flags, proc) != 0) {
        goto bad_fork_cleanup_kstack;
    }
    copy_thread(proc, stack, tf);

    bool intr_flag;
    local_intr_save(intr_flag);
    {
        proc->pid = get_pid();
        hash_proc(proc);
        set_links(proc);

    }
    local_intr_restore(intr_flag);

    wakeup_proc(proc);

    ret = proc->pid;
fork_out:
    return ret;

bad_fork_cleanup_kstack:
    put_kstack(proc);
bad_fork_cleanup_proc:
    kfree(proc);
    goto fork_out;
}

The process relationship is visualized as ：

                     +----------------+
                     | parent process |
                     +----------------+
              parent ^         \       ^  parent
                    /           \       \
                   /             \ cptr  \
                  /         yptr  V       \      yptr
           +-------------+  -->  +-------------+  -->  NULL
           | old process |       | New Process |
NULL  <--  +-------------+  <--  +-------------+
      optr                  optr

2.do_execve
① call exit_mmap(mm) and put_pgdir(mm) To reclaim all resources of the current process memory space （ Only reserved PCB）.
② call load_icode Allocate virtual memory space at a specific location according to the executable file .

// do_execve - call exit_mmap(mm)&put_pgdir(mm) to reclaim memory space of current process
//           - call load_icode to setup new memory space accroding binary prog.
int
do_execve(const char *name, size_t len, unsigned char *binary, size_t size) {
    struct mm_struct *mm = current->mm;
    if (!user_mem_check(mm, (uintptr_t)name, len, 0)) {
        return -E_INVAL;
    }
    if (len > PROC_NAME_LEN) {
        len = PROC_NAME_LEN;
    }

    char local_name[PROC_NAME_LEN + 1];
    memset(local_name, 0, sizeof(local_name));
    memcpy(local_name, name, len);
    // Free memory 
    if (mm != NULL) {
        lcr3(boot_cr3);
        if (mm_count_dec(mm) == 0) {
            exit_mmap(mm); // Delete the... Corresponding to the memory management PDT
            put_pgdir(mm);
            mm_destroy(mm);
        }
        current->mm = NULL;
    }
    // Load executable code , reset mm_struct, And reset trapframe
    int ret;
    if ((ret = load_icode(binary, size)) != 0) {
        goto execve_exit;
    }
    // Set the process name 
    set_proc_name(current, local_name);
    return 0;

execve_exit:
    do_exit(ret);
    panic("already exit: %e.\n", ret);
}

3.do_wait
① Check whether the memory area allocated by the current process is normal .
② Find specific / Whether there is a child process recycled by a waiting parent process in all child processes （PROC_ZOMBIE state ）. If so, the process will be recycled and return , If not, set the current process to PROC_SLEEPING And implement schedule Schedule other processes to run . After a child process of the current process finishes running , The current process will be awakened , And in do_wait Function to reclaim the child process PCB Memory resources .

// do_wait - wait one OR any children with PROC_ZOMBIE state, and free memory space of kernel stack
//         - proc struct of this child.
// NOTE: only after do_wait function, all resources of the child proces are free.
int
do_wait(int pid, int *code_store) {
    struct mm_struct *mm = current->mm;
    if (code_store != NULL) {
        if (!user_mem_check(mm, (uintptr_t)code_store, sizeof(int), 1)) {
            return -E_INVAL;
        }
    }

    struct proc_struct *proc;
    bool intr_flag, haskid;
repeat:
    haskid = 0;
    // If pid Not for 0, Then find the process id by pid A child process in a dead state of 
    if (pid != 0) {
        proc = find_proc(pid);
        if (proc != NULL && proc->parent == current) {
            haskid = 1;
            if (proc->state == PROC_ZOMBIE) {
                goto found;
            }
        }
    }
    // If pid by 0, Then you can find a process in a dead state 
    else {
        proc = current->cptr;
        for (; proc != NULL; proc = proc->optr) {
            haskid = 1;
            if (proc->state == PROC_ZOMBIE) {
                goto found;
            }
        }
    }
    if (haskid) { // If not , The parent process goes back to sleep 
        current->state = PROC_SLEEPING;
        current->wait_state = WT_CHILD;
        schedule();
        if (current->flags & PF_EXITING) {
            do_exit(-E_KILLED);
        }
        goto repeat;
    }
    return -E_BAD_PROC;
// Release all resources of the child process 
found:
    if (proc == idleproc || proc == initproc) {
        panic("wait idleproc or initproc.\n");
    }
    if (code_store != NULL) {
        *code_store = proc->exit_code;
    }
    local_intr_save(intr_flag);
    {
        unhash_proc(proc); // Remove child processes from hash_list Delete in 
        remove_links(proc); // Remove child processes from proc_list Delete in 
    }
    local_intr_restore(intr_flag);
    put_kstack(proc); // Release the kernel stack of the child process 
    kfree(proc); // Release the PCB
    return 0;
}

4.do_exit
① call exit_mmap,put_pgdir and mm_destroy To free up almost all the memory space of the process .
② Set the process state to dead mode , And then call wakeup_proc(parent) To let the parent process recycle this process .
③ call scheduler To switch to another process .

/ do_exit - called by sys_exit
//   1. call exit_mmap & put_pgdir & mm_destroy to free the almost all memory space of process
//   2. set process' state as PROC_ZOMBIE, then call wakeup_proc(parent) to ask parent reclaim itself.
//   3. call scheduler to switch to other process
int
do_exit(int error_code) {
    if (current == idleproc) {
        panic("idleproc exit.\n");
    }
    if (current == initproc) {
        panic("initproc exit.\n");
    }
    // Free up all memory space 
    struct mm_struct *mm = current->mm;
    if (mm != NULL) {
        lcr3(boot_cr3);
        if (mm_count_dec(mm) == 0) {
            exit_mmap(mm);
            put_pgdir(mm);
            mm_destroy(mm);
        }
        current->mm = NULL;
    }
    // Set the status of the current process to dead process 
    current->state = PROC_ZOMBIE;
    current->exit_code = error_code;
    // Request the parent process to reclaim the remaining resources 
    bool intr_flag;
    struct proc_struct *proc;
    local_intr_save(intr_flag);
    {
        proc = current->parent;
        if (proc->wait_state == WT_CHILD) {
            wakeup_proc(proc); // Wake up the parent process , The parent process is ready to recycle the process's PCB resources 
        }
        while (current->cptr != NULL) { // If the process has child processes , Set the parent process of all its child processes to init
            proc = current->cptr;
            current->cptr = proc->optr;
    
            proc->yptr = NULL;
            if ((proc->optr = initproc->cptr) != NULL) {
                initproc->cptr->yptr = proc;
            }
            proc->parent = initproc;
            initproc->cptr = proc;
            if (proc->state == PROC_ZOMBIE) {
                if (initproc->wait_state == WT_CHILD) {
                    wakeup_proc(initproc);
                }
            }
        }
    }
    local_intr_restore(intr_flag);
    // The process is completely over , Schedule other processes to run 
    schedule();
    panic("do_exit will not return!! %d.\n", current->pid);
}

5.syscall system call
syscall Is a way for kernel programs to provide kernel services for user programs .ucore The implementation of system calls in involves ：
（1） Initialize the interrupt descriptor for the system call
As early as lab1 In fact, this part is involved . stay ucore Initialization function kern_init Called in idt_init Function to initialize the interrupt descriptor table , And set an interrupt gate with a specific interrupt number , Dedicated for user process access to system calls . This matter is caused by ide_init Function completion ：

void
idt_init(void) {
    extern uintptr_t __vectors[];
    // Reference to... In another file __vectors
    for (int i = 0; i < 256; i++)
    SETGATE(idt[i], 0, GD_KTEXT, __vectors[i], DPL_KERNEL);
    // stay IDT Create interrupt descriptor in , It stores the code segment of the interrupt processing routine GD_KTEXT And offset __vectors[i], The privilege level is DPL_KERNEL. In this way, through the query idt[i] You can locate the starting address of the interrupt service routine .
    SETGATE(idt[T_SYSCALL], 0, GD_KTEXT, __vectors[T_SYSCALL], DPL_USER);
    // Set user status permissions for system call interrupt （DPL3）
    lidt(&idt_pd);
    // load LDT, the LDT Deposit in LDTR
}

（2） Set up the user library for system call
Initialize the interrupt descriptor related to the system call in the operating system 、 After interrupt processing start address, etc , You also need to initialize the related work in the user mode application , Simplify the complexity of application access system calls . For this purpose, an intermediate layer is established in the user mode , That is, simplified libc Realization , stay user/libs/ulib.[ch] and user/libs/syscall.[ch] It completes the encapsulation of accessing system calls . The final access system call function in user mode is syscall, The implementation is as follows ：

static inline int
syscall(int num, ...) {
    va_list ap;
    va_start(ap, num);
    uint32_t a[MAX_ARGS];
    int i, ret;
    for (i = 0; i < MAX_ARGS; i ++) {
        a[i] = va_arg(ap, uint32_t);
    }
    va_end(ap);

    asm volatile (
        "int %1;"
        : "=a" (ret)
        : "i" (T_SYSCALL),
          "a" (num),
          "d" (a[0]),
          "c" (a[1]),
          "b" (a[2]),
          "D" (a[3]),
          "S" (a[4])
        : "cc", "memory");
    return ret;
}

This function sets %eax, %edx, %ecx, %ebx, %edi, %esi The values of the five registers are syscall Call number 、 Parameters 1、 Parameters 2、 Parameters 3、 Parameters 4、 Parameters 5, And then execute int The interrupt enters the interrupt processing routine .

（3） The execution of system calls
In the interrupt handling routine , The program will , perform syscall function （ Pay attention to syscall Functions are kernel code , Not in the user library syscall function ）. kernel syscall The function retrieves the values of the six registers one by one , And execute different system calls according to the system call number . The essence of those system calls is that of other kernel functions wrapper. The following is a syscall Function implementation code ：

void
syscall(void) {
    struct trapframe *tf = current->tf;
    uint32_t arg[5];
    int num = tf->tf_regs.reg_eax;
    if (num >= 0 && num < NUM_SYSCALLS) {
        if (syscalls[num] != NULL) {
            arg[0] = tf->tf_regs.reg_edx;
            arg[1] = tf->tf_regs.reg_ecx;
            arg[2] = tf->tf_regs.reg_ebx;
            arg[3] = tf->tf_regs.reg_edi;
            arg[4] = tf->tf_regs.reg_esi;
            tf->tf_regs.reg_eax = syscalls[num](arg);
            return ;
        }
    }
    print_trapframe(tf);
    panic("undefined syscall %d, pid = %d, name = %s.\n",
            num, current->pid, current->name);
}

After the corresponding kernel functions are completed , Reserved before the program passes trapframe Return to user status , A system call ends .

analysis fork/exec/wait/exit How the implementation affects the execution state of the process

①fork Will change the status of its child processes to PROC_RUNNABLE, The current process state does not change .
②exec Do not modify the status of the current process , But it will replace all the data and code in the memory space .
③wait It will first detect whether there are child processes . If there is, enter PROC_ZONBIE Can be inherited by child processes. , The process is recycled and the function returns . But if the existence is still in PROC_RUNNABLE Can be inherited by child processes. , The current process will enter PROC_SLEEPING state , And wait for the child process to wake up .
④exit Will set the current process status to PROC_ZONBIE, And wake up the parent process , Make it in PROC_RUNNABLE The state of , Then take the initiative to give up CPU.

Please give me ucore Execution state lifecycle diagram of a user state process in （ Package execution status , Execute the transformation relationship between states , And the event or function call that produces the transformation ）

Experimental experience

Until Experiment 4 ,ucore Still in a nuclear mindset “ Spin ”, It is not executed in user mode . therefore , Experiment 5 is to provide a mechanism for creating and executing user state processes , Provide a user mode running environment for application execution . The user mode operating environment , It is necessary to build from two aspects: storage space and execution instructions . The storage space aspect is to limit the physical address space that the user process can access , And the physical memory space access between user processes does not overlap . In terms of executing instructions, it is to restrict the executable instructions of the user process , You cannot let a user process execute privileged instructions , This ensures that the user process cannot destroy the system . Join to execute privileged instructions , Complete some functions , You need to apply to the system , Let the system help complete , This is the system call . And the running state of user mode , In fact, it is very different from the kernel thread . So this experiment is to let us understand how the user state process is implemented .