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

An Overview of Kernel Virtual Memory

Follow up the GDT and Protected Mode article, which will be the focus of the Loader. First of all, we need to set up the virtual memory of kernel space. If you are not familiar with the principle of virtual memory, be sure to teach yourself, there is a documentation available here for reference.

So far we’ve been working on physical memory, or 1MB of low address space to be exact, and it’s all pretty straightforward. But then the loader will be ready to load the kernel and we need to plan the data and code on the larger 4GB virtual memory space.

Modeled after Linux, we will use 3GB or more of the high address space as kernel space for all subsequent work. For example, at the most basic level, the current physical low address 1MB will be mapped to virtual address 0 ~ 1MB and 3GB above 0xC0000000 ~ (0xC0000000 + 1MB) :

After entering the kernel, access to the lower 1MB space will use the virtual address 0xC0000000 ~ (0xC0000000 + 1MB), which mainly includes the currently used stack and the corresponding memory map of the display:

So the video memory base address will start from the virtual address 0xC00B8000, but we don’t need to go into that for now, we will discuss that in the Display and Print article later.

In addition to the basic low 1MB memory space, the loader also needs to further expand the virtual space above 0xC0000000, which mainly includes two parts:

  • The page directory used by the kernel (page directory) and the page table (page table);
  • Read kernel binary image, and load code and data;

The following diagram shows the virtual-to-physical memory mapping to be built during the whole loader phase:

This is one of the most important global graphs of this article. The second row is a “warped” diagram of the first row. We have reduced the user space below 3GB, focusing on the kernel space above 3GB (the thick box) for the moment. Since it is a virtual address space, our space partition can be relatively arbitrary and “luxurious”. We divide the virtual space into the following regions starting from 0xC0000000 with 4MB as the unit:

  • The first 4MB is reserved, where the lower 1MB is mapped to the lower 1MB of the physical address, as explained above;
  • The second 4MB (orange) is used to map all of the kernelpage tables;
  • The third 4MB (green) is from0xC0800000Start as load and storekernelCode and data space, that iskernelAddressing starts at that point;

It should be noted that there is no set way to implement an OS, and this is just my personal way of doing it. As a matter of fact, memory planning is very flexible. Just like the name scroll of this project, memory is a picture scroll, while CPU is a brush. Under the premise of following certain rules, you can make free use of it.

Let’s start with the orange part, the kernel Page Directory and Page Tables.

Set up the kernel virtual memory

Before we start this section, let’s review the principles of Page Directory and Page Table.

Some key numbers to keep in mind:

  • Page (pageIs 4096;
  • Page directory entrypde (page directory entry)And a page table entrypte (page table entry), which is essentially the same structure, of magnitude zero4 bytes;
  • page direcotryThere are 1024 entries. There are 1024 entriespage table, a total of4MB;
  • eachpage tableThey both have 1024 entries. They point to 1024 entriespagesManagement of the1024 * 4KB = 4MBThe virtual space of;
  • So eachpdeManages the4MBThe virtual space of;

All right, let’s set up the page table for the kernel space. By convention, this section of related code starts with the setup_page function for your reference.

From here on out, as a terminology convention, I’ll describe virtual pages as pages, and physical pages as frames.

Build the page directory

First we need to take out a frame that will be used as the Page Directory. Going back to the diagram of physical memory distribution, the part below 1MB is currently occupied, and the part we can use starts from 1MB (0x100000).

I chose 0x100000 + 4KB, i.e., the second frame after 0x100000 as the page directory. Of course, this is a personal choice; The first frame after 0x100000 I chose this as the first page table:

Again, this is my personal choice; The choice of frame is very free, as long as it has not been occupied can be used, of course, you have to remember which frames you have used, reasonably compact and try to “aesthetically” plan the use.

Map 1MB of low memory space

It is worth noting that both the 0th and 768th PDEs point to the same page table that we will use to map 0-1MB of low memory, which is the 1MB memory space we are currently in. Of course, this page table can manage 4MB of space, we only mapped 1MB of it, the remaining 3MB of virtual space is idle, but it doesn’t matter, it is idle, but it is virtual space.

The following figure shows how the lower 1MB memory is mapped in the page table:

PDE [0] manages the lowest 4MB of virtual space, where the first 1MB is mapped to the lower 1MB of physical space. This is a one-to-one mapping. Virtual addresses are exactly equal to physical addresses, so after turning on Paging, Our access to 1MB of low memory is changed to use virtual addresses, just like the previous physical address access, and no change is perceived.

PDE [768] manages the first 4MB starting at 0xC0000000, or 3GB. Going back to the first figure at the beginning of this article, its first 1MB is also mapped to the lower 1MB. After turning on paging and entering the kernel, we will access the low 1MB memory with 0xC0000000 ~ 0xC0000000 + 1MB:

Map Page Directory and Page Tables themselves

Here is the point and difficulty of this section. We know that page directory and page tables refer to physical pages, but once paging mode is turned on, all memory access will be through virtual addresses, and we can no longer directly manipulate physical addresses. So how do we access and modify the Page Directory and Page Tables themselves?

One way, of course, would be to turn off paging when needed and go directly to the physical address. The previous recommended Jamesm’s Kernel Development Tutorials do this in many places, but this is not a good practice for several reasons:

  • After entering the complex kernel, code execution involves a lot of memory access such as stack and heap, as well as other global variables, all of which are virtual addresses in the kernel space. If paging is turned off suddenly, access to them will not be possible. You have to be very careful about how your code accesses memory, or there will be unpredictable consequences, but this is very difficult to do;
  • Once multithreading is turned on, if there is an interrupt while paging is turned off, the CPU does some automatic stack and interrupt handling, all on virtual addresses. The results are obviously disastrous.

A more logical approach would be to map the Page Directory and Page Tables themselves to the virtual space, so that they can be accessed just like any other normal memory. Page Directory and Page Tables are essentially pages, just like any other memory access. The question is, how do you create this mapping? Take a look at the picture below:

We point pde[769] to the frame itself of Page Directory. Thus the page direcotry also acts as a page table, managing exactly 1024 page tables themselves, for a total of 4MB. One of the 1024 Page Tables is Page direcotry itself.

Isn’t it a little twisted? In other words, since PDE [769] points to the page directory itself, the 4MB virtual space from 0xC0400000 to 0xC0800000 is now mapped to 1024 page tables, And even better, their virtual addresses are completely contiguous and tightly packed into the 4MB space.

Thus, the problem above has been resolved, and the corresponding virtual address space for Page Tables is:

0xC0400000 ~ 0xC0800000

This is the 769th 4MB of 4GB space (out of a total of 1024 4MB Spaces that make up 4GB).

And we also get the page directory which has its own virtual address:

0xC0701000

0xC0400000 ~ 0xC0800000 769th page in 4MB space, isn’t it ingenious 🙂

The core idea here is that the Page Directory is essentially a special Page Table that manages 4MB of space just like any other Page Table.

If you still feel a little confused, you may as well verify it in reverse. Starting from the virtual address given above, you can deduce where the physical address is actually pointed to. I think the logic behind this can be clarified soon.

And if you think about it a little bit more, it’s not the only way to do it. Instead of choosing PDE [769], you can use another virtual space to map page tables, such as PDE [770]. The virtual space for all page tables becomes 0xC0800000 to 0xC0C00000. Using PDE [769] is only my personal choice, because it is the second 4MB space after 0xC0000000. With this arrangement, the virtual space can be used a little more compact and tidy.

Map other areas of the kernel space

So far, PDE 768 and 769 have been used, i.e., two 4MB Spaces 0xC0000000 ~ 0xC0400000 and 0xC0400000 ~ 0xC0800000 have been requisitioned. For the remaining 254 page tables corresponding to PDE [770] ~ PDE [1023], we arranged the frames for them in turn. In this way, we ended up requisitioned 256 Pages & Frames, with a total of 1MB of virtual & physical memory, to build the page tables of the kernel space (3GB ~ 4GB) and manage the 1GB space.

We pull out the orange part of the virtual-to-physical memory map at the beginning of this chapter to show the memory distribution of the 256 page tables in the kernel:

Note that we only allocated kernel space, i.e., page tables with a size of 3GB or more, 256 pages and a space of 1MB, They also map the last quarter of the space between 0xC0400000 and 0xC0800000, namely, between 0xC0700000 and 0xC0800000. For user space below 3GB, page tables are not allocated at this time because we are not currently using them.

These 256 kernel page tables (one of which is the Page Directory itself) are the most core page tables during the writing of the kernel. PDE [768] and PDE [1023] are all 256 entries in the page directory, which refer to the page tables.

In fact, except for the first two page tables, the last 254 are currently empty and not used. We just arrange frames for them. This used up a good 1MB of physical memory, which seemed a bit of a luxury, given that the total physical memory in the project configuration was only 32MB (see Bochsrc. TXT, although today’s computers have far more than 32MB of physical memory, which is no longer a problem). One very important reason for this is that the 256 kernel page tables are then shared by all processes, meaning that the space below 3GB is isolated to user processes. As a matter of course, more than 3GB of kernel space is shared, otherwise there would be multiple kernels running independently in memory.

Each time a new process is fork, the last quarter of its page directory (768 ~ 1023) will directly copy the page directory (768 ~ 1023) of the kernel. Point to the 256 kernel page tables. So we require the frames of the 256 page tables to be fixed from the beginning and not to change in the future so that we can achieve the effect shared by all processes.

Open the paging

With the page tables in place, you can turn on paging:

enable_page:
  sgdt [gdt_ptr]

  ; move the video segment to > 0xC0000000
  mov ebx, [gdt_ptr + 2]
  or dword [ebx + 0x18 + 4], 0xC0000000

  ; move gdt to > 0xC0000000
  add dword [gdt_ptr + 2], 0xC0000000

  ; move stack to > 0xC0000000
  mov eax, [esp]
  add esp, 0xc0000000
  mov [esp], eax

  ; set page directory address to cr3 register 
  mov eax, PAGE_DIR_PHYSICAL_ADDR
  mov cr3, eax
  
  ; enable paging on cr0 register
  mov eax, cr0
  or eax, 0x80000000
  mov cr0, eax

The most important thing here is to set the CR3 register to point to the FRAME of the Page Directory (note the Physical address) and then turn on the Paging bit switch on the CR0 register.

conclusion

At this point, the Loader phase about kernel virtual memory initialization ends. This section of code is not long, the core is just setup_page function, but the principle behind it is very deep and complex. In the loader stage, the framework of Virtual Memory is preliminarily established, which lays a good foundation for memory management after entering kernel.

At the current stage, all of our virtual-to-physical memory allocation and mapping are planned in advance for pre-allocation and reuse, and each physical frame is arranged manually. This is not really a full use of Virtual Memory. After entering the kernel, we will further improve the work related to Virtual Memory, including the handling of page faults, the copying of the process page directory, and so on.

Virtual memory processing is the underlying core work throughout the kernel implementation and operation, must be guaranteed to be absolutely correct and stable. Once something goes wrong, the system will immediately appear all kinds of strange and unpredictable errors and even crash, and debugging is very difficult.

In the next post we will load the actual kernel into memory and go to the kernel to start executing the code, which will be the last level before entering the kernel.