Write the OS kernel-process implementation from scratch

Series directory

introductory
The preparatory work
BIOS starts in real mode
GDT and Protected Mode
Exploration of Virtual Memory
Load and enter the kernel
Display and print
The global descriptor table GDT
Interrupt handling
Virtual memory improvement
Implement heap and malloc
The first kernel thread
Multi-threading running and switching
The lock is synchronized with multithreading
Enter user mode
Implementation of a process
The system calls
Simple file system
Load the executable program
The keyboard driver
To run a shell

Process the Process

In the previous installments, we set up a framework for Thread to run and schedule. At the beginning of this article we will implement the management of process on top of Thread.

The concept and difference between thread and process is a cliche, and I don’t want to repeat it here. For a small project like Scroll, Thread is the key, the skeleton, because Thread is the basic unit of task operation; Process is just a higher layer of one or more threads, which is more responsible for the management of resources. For example, in Linux system, the contents of each process management include:

Virtual memory;
File descriptor;
Signal mechanism;
.

Our project is relatively simple and will not involve complex file systems and signals, so the main responsibility of process is memory management. This article first defines the structure of process, and then focuses on its two functions:

User Stack Management;
Page management;

In the next few chapters, we will further show how the OS loads and runs a user-executable program, along with the implementation of system calls such as fork/exec, which are process-oriented operations.

The process structure

Define process_struct, which in Linux is called PCB (process control block) :

struct process_struct {
  uint32 id;
  char name[32];
  enum process_status status;
  // map { tid -> threads }
  hash_table_t threads;
  // allocate user space stack for threads
  bitmap_t user_thread_stack_indexes;
  // exit code
  int32 exit_code;
  // page directory
  page_directory_t page_dir;
};

typedef struct process_struct pcb_t;

Only the most important fields are listed here, so the comments should be clear. For the time being, such a simple structure suffices.

The user stack allocation

As we mentioned in the last article, each process has its own stack on the user space, so the process is responsible for allocating the position of the stack to its threads. This is quite simple. These stacks are stacked near the bottom of the 3GB stack:

For example, if we specify a stack top position and each stack is 64 kilobytes, then allocating the stack is very simple and can be done with just one bitmap:

#define USER_STACK_TOP 0xBFC00000 // 0xC0000000 - 4MB #define USER_STACK_SIZE 65536 // 64KB struct process_struct { // . bitmap_t user_thread_stack_indexes; / /... }

As you can see in the create_new_user_thread function, the stack is allocated for the user thread:

// Find a free index from bitmap. uint32 stack_index; yieldlock_lock(&process->lock); if (! bitmap_allocate_first_free(&process->user_thread_stack_indexes, &stack_index)) { spinlock_unlock(&process->lock); return nullptr; } yieldlock_unlock(&process->lock); // Set user stack top. thread->user_stack_index = stack_index; uint32 thread_stack_top = USER_STACK_TOP - stack_index * USER_STACK_SIZE;

Notice that this is locked, because there may be multiple threads competing under a process.

Page management

Another important job of process is managing the virtual memory of the process. We know that virtual memory is isolated as processes, each of which holds its own Page Directory and Page Tables. If a thread’s process changes during a Threads switch, the page directory needs to be reloaded. This is shown in the context switch for the Scheduler:

void do_context_switch() { // ... if (old_thread->process ! = next_thread->process) { process_switch(next_thread->process); } / /... } void process_switch(pcb_t* process) { reload_page_directory(&process->page_dir); }

Copy the page table

Obviously, each process needs to create its own page directory at the time of creation, but in general, except for a few original kernel processes when the kernel is initialized, new processes are all forked from the existing process. This is especially true of the user state Process.

As an aside, have you ever wondered why the process has to come out of an existing fork? Can’t you just create it out of nothing and load it into a new program and run it? If you are a parent or a child process, and in most cases it is a combination of fork and exec, you should know how to use fork and programming paradigm in Linux. Why not just make a system call like this:

int create_process(char* program, int argc, char** argv)

It is a perfect replacement for the fork + exec pairing.

This inside has the UNIX history reason, also has its design philosophy consideration, the net can search under has a lot of discussion, some people like some people oppose, is a difficult to pull the clear question. Since we’re newbies, let’s fork the process, just like UNIX.

The full implementation of fork will be covered in detail in a later article on system calls. This article will cover only one very important step in the fork process, which is the copy of the page table. The child’s page table is copied from the parent’s page table. The parent’s page table is copied from the parent’s page table. The parent’s page table is copied from the parent. The contents are exactly the same, which is beneficial in terms of saving memory resources.

However, if the child is a read memory, it is fine. If a write operation occurs, then the child and child cannot share the memory and must go their separate ways. This involves the copy-on-write technique of virtual memory, which is also implemented here.

The code used in this section is primarily the clone_crt_page_dir function.

The first thing to do is to create a new Page Directory of one page size, which is assigned a physical Frame and a virtual Page, note that the Page must be aligned with Page, and then manually map them. This new Page Directory can be accessed directly from the virtual address.

int32 new_pd_frame = allocate_phy_frame();
uint32 copied_page_dir = (uint32)kmalloc_aligned(PAGE_SIZE);
map_page_with_frame(copied_page_dir, new_pd_frame);

Next set up the mapping of Page Tables for the new Page Directory. As mentioned earlier, all processes share the kernel space, so the 256 page tables in the kernel space are shared:

PDE [768] ~ PDE [1023] = PDE [768]; PDE [1023] = PDE [768]; PDE [1023] = PDE [1023];

pde_t* new_pd = (pde_t*)copied_page_dir; pde_t* crt_pd = (pde_t*)PAGE_DIR_VIRTUAL; for (uint32 i = 768; i < 1024; i++) { pde_t* new_pde = new_pd + i; if (i == 769) { new_pde->present = 1; new_pde->rw = 1; new_pde->user = 1; new_pde->frame = new_pd_frame; } else { *new_pde = *(crt_pd + i); }}

Notice, however, that one PDE is special, and that’s term 769. As explained in the introduction to virtual memory, the 769th PDE, the 769th 4MB space in the 4GB space, is used to map 1024 page tables themselves, so entry 769 needs to point to the page directory of the process:

After processing the kernel space, the next step is to copy the page tables in the user space. Each Page Table here needs to be copied out, and then set the PDE in the new Page Directory to point to it. Note that only the Page Table is copied, not the pages managed by the Page Table, so the virtual memory used by the parent and child processes is virtually identical:

int32 new_pt_frame = allocate_phy_frame();

// Copy page table and set ptes copy-on-write.
map_page_with_frame(copied_page_table, new_pt_frame);
memcpy((void*)copied_page_table,
       (void*)(PAGE_TABLES_VIRTUAL + i * PAGE_SIZE),
       PAGE_SIZE);

As with Page Directory, we manually allocate the physical frame and virtual page, and set up the mapping. All memory operations use virtual addresses.

The next critical step is to introduce copy-on-write since the parent and child processes share all of the virtual memory in user space, but need to separate them when writing. This means that all valid PTEs in the parent and child page table are temporarily marked as read-only. Whoever tries to write will trigger the page fault. In the Page Fault Handler, this page will be copied. Then make the PTE point to the newly copied page, thus achieving isolation:

// Mark copy-on-write: increase copy-on-write ref count. for (int j = 0; j < 1024; j++) { pte_t* crt_pte = (pte_t*)(PAGE_TABLES_VIRTUAL + i * PAGE_SIZE) + j; pte_t* new_pte = (pte_t*)copied_page_table + j; if (! new_pte->present) { continue; } crt_pte->rw = 0; new_pte->rw = 0; int32 cow_refs = change_cow_frame_refcount(new_pte->frame, 1); }

Copy-on-write exception handling

When a copy-on-write page fault is triggered, the page fault handler will have to handle the problem. The page fault handler will have to handle the problem.

Note that this type of page fault occurs when:

if (pte->present && ! pte->rw && is_write)

That is, the page is mapped, but is marked as read-only, and the operation that is currently causing the page fault is a write operation.

We use a global hash table that holds how many times the frame has been forked, i.e. how many processes it is currently shared by. Every time we do copy-on-write, we decrement its reference count by one. If there are still references, we need to copy. Rw = true; rw = true; rw = true; rw = true; rw = true;

int32 cow_refs = change_cow_frame_refcount(pte->frame, -1);
if (cow_refs > 0) {
  // Allocate a new frame for 'copy' on write.
  frame = allocate_phy_frame();
  void* copy_page = (void*)COPIED_PAGE_VADDR;
  map_page_with_frame_impl((uint32)copy_page, frame);
  memcpy(copy_page,
         (void*)(virtual_addr / PAGE_SIZE * PAGE_SIZE),
         PAGE_SIZE);
  pte->frame = frame;
  pte->rw = 1;

  release_pages((uint32)copy_page, 1, false);
} else {
  pte->rw = 1;
}

conclusion

This article is just the beginning of Process, which mainly defines the basic data structure of Process and realizes the memory management function of Process, which is also one of the most important responsibilities of Process in this project. In the next few articles we’ll start to actually create the process, and we’ll run it by loading the user executable from disk, the classic combination of fork + exec system calls.

Write the OS kernel-process implementation from scratch

Series directory

Process the Process

The process structure

The user stack allocation

Page management

Copy the page table

Copy-on-write exception handling

conclusion

Related Posts

Write OS kernel from scratch – lock synchronization with multithreading

Bugs written in those years [0]

Arrays in the C language