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
  • Multithreading switch
  • The lock is synchronized with multithreading
  • Implementation of a process
  • Enter user mode
  • A simple file system
  • Load the executable program
  • Implementation of system calls
  • The keyboard driver
  • To run a shell

Open up virtual space

In the chapter of Virtual Memory Exploration, we have preliminarily established the framework of virtual memory for kernel in the loader stage, including Page Directory, Page Table and so on. In that article, we have carved out its first three 4MB of kernel space above 0xC0000000 and manually specified their functionality:

  • 0 xc0000000 ~ 0 xc0400000: 1MB less memory at the beginning of the mapping;
  • 0 xc0400000 ~ 0 xc0800000: a page table;
  • 0 xc0800000 ~ 0 xc0c00000: kernel loading;

At this stage, all the memory is planned manually, and virtual-to-physical mapping is also allocated manually, which is certainly not a long-term solution. Subsequent virutal memory will be allocated dynamically in a more flexible manner, and mapped physical memory will no longer be allocated in advance, but will be drawn on demand, which will require page fault handling.

Missing page exception

We tried to trigger a page fault at the end of the interrupt processing in the last article, but the handler is just a demo that doesn’t really solve the page fault problem. Let’s solve it now.

The Page Fault addresses two core issues:

  • Determine the virtual address where the page fault occurred, and the type of exception;
  • Assign a physical frame and create a map;

Details of page faults

The first question is easy, let’s just look at the code:

void page_fault_handler(isr_params_t params) {
  // The faulting address is stored in the CR2 register
  uint32 faulting_address;
  asm volatile("mov %%cr2, %0" : "=r" (faulting_address));

  // The error code gives us details of what happened.
  // page not present?
  int present = params.err_code & 0x1;
  // write operation?
  int rw = params.err_code & 0x2;
  // processor was in user-mode?
  int user_mode = params.err_code & 0x4;
  // overwritten CPU-reserved bits of page entry?
  int reserved = params.err_code & 0x8;
  // caused by an instruction fetch?
  int id = params.err_code & 0x10;
  
  // ...
}
  • The address of the page fault is stored incr2Register;
  • The type of page fault, along with other information, is stored inerror code;

Remember the error code? As mentioned in the previous interrupt handling article, the CPU will automatically push the error code onto the stack to record some information about the exception when it occurs. Page fault is one such example:

The error code is easy to get, it’s in the parameter isr_params_t of page_fault_handler, remember this struct? This corresponds to the interrupt context stack in green, which is passed as an argument to the interrupt handler in pink:

typedef struct isr_params {
  uint32 ds;
  uint32 edi, esi, ebp, esp, ebx, edx, ecx, eax;
  uint32 int_num;
  uint32 err_code;
  uint32 eip, cs, eflags, user_esp, user_ss;
} isr_params_t;

Page_fault_handler is the parser of the error code, which records a lot of useful information. There are two fields that are important to us:

  • present: Page fault because the page is not allocated?
  • rw: The command that triggered the page fault. Is the memory access operation write?

They correspond to two bits of the page table entry:

  • presentIt is easy to understand that if it is 0, it means that the page is not mapped to a physical frame, and it will cause a page fault, which is the most common cause of a page fault.
  • But even if the present bit is 1, but the rw bit is 0, if you write to memory at this time, there will be a page fault. We need to do something special for this case. This will happen later in the processforkUsed incopy-on-writeTechnical details;

Assign a physical frame

We planned the allocation of physical memory manually before and it was neat. At present, 0 ~ 3MB of space has been used up. However, starting from the back, we need to establish the data structure for the remaining frames to manage them, with no more than two requirements:

  • Distribution frame;
  • Return the frame;

So you need a data structure to keep track of which frames have been allocated and which are still available, and here you use a bitmap to do that. Hopefully, Bitmap is not new to you. It uses a series of bits, each of which represents a true/false, to indicate whether or not the frame has been used.

Of course, as a poor kernel project, Bitmap needs to be implemented by yourself. My simple implementation code is in SRC /utils/bitmap.c. You can see the SRC /utils directory that contains the various data structures I implemented, which will be used later.

typedef struct bit_map {
  uint32* array;
  int array_size;  // size of the array
  int total_bits;
} bitmap_t;

My bitmap is very simple, using an array of ints for storage:

The assignment is also very simple and crude, you start at 0 and you find it one by one. Of course it has a worst-case O(N) time complexity, but performance is not yet a consideration for this project, and our goal for now is to be simple and correct.

And this is a layer problem: our bitmap is designed to solve the page fault, and it is difficult to implement a complex data structure when the page fault has not been solved and dynamic memory allocation based on heap has not been implemented. Complex data structures inevitably involve dynamically allocating memory, which can cause page faults at any time, and we’re back to square one.

So a simple, pre-allocated static memory data structure is the simplest and most efficient way for us to implement it. The bitmap and its internal array are global variables defined in SRC /mem/paging. These variables have been compiled into the kernel and are part of the data or BSS segment, so allocating memory is not a problem.

static bitmap_t phy_frames_map;
static uint32 bitarray[PHYSICAL_MEM_SIZE / PAGE_SIZE / 32];

Note that the size of the array is PHYSICAL_MEM_SIZE/PAGE_SIZE / 32, which should be easy to understand.

So assigning a frame is pretty simple, just a bitmap operation:

int32 allocate_phy_frame() { uint32 frame; if (! bitmap_allocate_first_free(&phy_frames_map, &frame)) { return -1; } return (int32)frame; } void release_phy_frame(uint32 frame) { bitmap_clear_bit(&phy_frames_map, frame); }

To deal with page fault

With everything in place, we’re ready to deal with the page fault. Page_fault_handler calls the map_page function:

page_fault_handler
  --> map_page
    --> map_page_with_frame
      --> map_page_with_frame_impl

Finally, we come to map_page_with_frame_impl. This function is a little longer, but the logic is quite simple. It is annotated with pseudocode:

find pde (page directory entry)
if pde.present == false:
    allocate page table

find pte (page table entry)
if frame not allocated:
    allocate physical frame

map virtual-to-physical in page table

The PDE and PTE data structures are defined in SRC /mem/paging,h. With the help of C, everything is very convenient. You don’t have to look at bits like you did in the loader before:)

Note that we use virtual addresses for page direcotry and page tables, which we focused on earlier in the tutorial on virtual memory:

  • page directoryThe address for0xC0701000;
  • page tablesA total of 1024 in the address space0xC0400000 ~ 0xC0800000In order;

Virtual memory processing for process fork

The code also involves copy-on-write to the RW and a copy of the entire virtual memory of the current process, which is later used when the process system calls fork. To put it simply, when a process forks, it does several things to the virtual memory:

  • Copy the entirepage directory 和 page tables, so that the memory space of the new process is actually a mirror of the old process;
  • The kernel space of the new and old processes is shared, while the memory of the user space is usedcopy-on-writeMechanism isolation;

We will not do this in this article. We will fill in the hole later when the system calls fork.