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
  • A simple file system
  • Load the executable program
  • Implementation of system calls
  • The keyboard driver
  • To run a shell

User mode thread

In the previous articles, we have started kernel threads and implemented multi-threads scheduling. Next we need to start the user thread. After all, the OS is for users, and most future Threads will be user mode as well.

Here we need to clarify the relationship between user and kernel thread/stack. Some students may lack an intuitive understanding of this.

  • Each user thread will have two stacks, namely, the stack in the user space and the stack in the kernel space.
  • The normal user thread runs on the user stack.
  • When an interruption occurs (includinginterrupt / exception / soft int), the execution stream jumps to the thread kernel stack to start executing interrupt handler, and returns to the user stack to resume execution after the execution is completed;

Start from the kernel thread

To be clear, user threads don’t appear out of thin air. Essentially, they still need to run from the kernel thread and jump to the user’s code + stack. So here is a review of the kernel thread startup process, which was explained in detail in the first kernel thread article. The most core work here is the initialization of kernel stack. We build a stack as shown in the figure below:

Then it starts running from the RESUME_THREAD instruction, the stack initial position starts POP from KERNEL_ESP, initializes each general purpose register, and jumps to the function KERNEL_THREAD through the RET instruction. You can see that the kernel thread finally runs into the kernel_thread worker function and always runs on the kernel stack (light blue).

How do I get to User

From kernel to user mode, there are two problems to be solved:

  • How to jump to user code run, here need to change the CPU privilege level, from 0 -> 3;
  • How to jump to the user stack, which is under 3GB of user space;

As for problem 1, it is important to note that this is not something that can be done with a normal JMP or CALL directive. The only way to reduce CPU privilege on x86 architecture is from interrupt return, namely IRET instruction;

For problem 2, you need to pay attention to the stack entered into user space, and change the SS register value to refer to user’s data segment (you may need to review the knowledge of segment, initialized in global descriptor GDT).

So the user thread is essentially initialized to simulate a return from an interrupt. If you remember the structure of the interrupt stack from the Interrupt Handling section:

Interrupts can be pushed by the CPU and by the interrupt handler when the interrupt handler starts up. The interrupt stack is described as follows:

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;

typedef isr_params_t interrupt_stack_t;

Here we redefine it as an interrupt_stack_t structure, which we’ll use later to denote the interrupt stack;

Note the stack part of automatic CPU push, which actually solves both of these problems:

  • The user code is saved incs 和 eip;
  • The location of the user stack is stored inuser esp 和 user ss;

Once IRET is called, this stored data pops out and jumps automatically, so we can actually just build one of these interrupt_stack_t structures in the kernel stack and set those values and come back in a simulated interrupt, Enable this to help us “return” to the User state.

By convention, the main source code of this article is given, which is mainly the following functions:

  • create_new_user_thread
  • init_thread
  • prepare_user_stack

The init_thread function is used to initialize the kernel thread, and is now used to further initialize the user thread by switching the user control on and off with a single argument. User Threads must also evolve from the kernel Threads.

Prepare the kernel stack

Here is a review of the initialization of the kernel stack in the kernel thread:

Notice the User Interrupt Stack in the dashed line at the top, which we did not touch when the kernel thread started because it was not used by the kernel thread, and now we need to populate it with the interrupt_stack_t structure above.

Look at the init_thread function initializing this part:

interrupt_stack_t* interrupt_stack = (interrupt_stack_t*)((uint32)thread->kernel_esp + sizeof(switch_stack_t)); // data segemnts interrupt_stack->ds = SELECTOR_U_DATA; // general regs interrupt_stack->edi = 0; interrupt_stack->esi = 0; . // user-level code env interrupt_stack->eip = (uint32)function; interrupt_stack->cs = SELECTOR_U_CODE; interrupt_stack->eflags = EFLAGS_IOPL_0 | EFLAGS_MBS | EFLAGS_IF_1; // user stack interrupt_stack->user_ss = SELECTOR_U_DATA;

First, the location of the interrupt_stack with a switch_stack_t structure size above the initial kernel_esp was correctly located.

The next step is to initialize the various registers in the interrupt stack:

  • dsInitialized to the user spacedata segment;
  • The universal register is initialized to 0;
  • csInitialized to the user spacecode segment;
  • eipInitialize the worker function of the User Thread, which was passed in when the Thread was created.
  • eflagsInitialization;
  • user_ssAlso initialized to the user spacedata segment;
  • user_espUninitialized, where does it go? ! We will not initialize the stack because the location of the user stack is still to be determined, and its initialization will be discussed later.

Start Run Thread

As mentioned above, user threads also need to start from the kernel thread, so they start in the same way. The difference is that thread_entry_eip is set to the initial entry point of the entire thread.

By contrast, if the kernel thread is running, then thread_entry_eip is set to the kernel_thread worker; The switch_to_user_mode function is set to the switch_to_user_mode function. The code is simple:

switch_to_user_mode:
  add esp, 8
  jmp interrupt_exit

Recall that the kernel thread starts running at the kernel_esp position on the stack, pops all the universal registers, and then the ret pops to start_eip (thread_entry_eip). This is the switch_to_user_mode function; Then add ESP (8) to the User Interrupt Stack (8), so that ESP finally reaches the User Interrupt Stack (8) correctly:

Then we start executing the interrupt_exit function, which is the lower half of the interrupt handler isr_common_stub, which exits the interrupt and resumes the context before the interrupt occurred:

interrupt_exit:
  ; recover the original data segment
  pop eax
  mov ds, ax
  mov es, ax
  mov fs, ax
  mov gs, ax

  popa
  ; clean up the pushed error code and pushed ISR number
  add esp, 8

  ; make sure interrupt is enabled
  sti
  ; pop cs, eip, eflags, user_ss, and user_esp by processor
  iret

In combination with the diagram of the UserInterrupt Stack, you can see that it begins to “restore” (not really restore, we initialize the constructed User Context). It addresses the two issues mentioned earlier, and is essentially the two core elements of Thread that we’ve highlighted:

  • The user code (cs + eip)
  • The user stack (user ss + user esp)

The user context also contains the user data segment, general registers, eFlags, etc., all of which are initialized here. At this point, the runtime environment for the User Thread is initialized.

This section may seem a bit confusing at first, but you need to review the segment, interrupt and kernel thread initialization and start procedures. In essence, we need to understand the functions of the two Stacks on kernel stack:

  • switch stack: This is the stack used to run code in kernel mode. All kernel code about this thread runs here, and the context switch between multi-threads also occurs here.
  • interrupt stack: This is the user state into and out of the kernel state interrupt stack, which is built by the CPU and interrupt handler when an interrupt occurs;

The user thread initialization process is essentially divided into two steps:

  • At first, just like the kernel thread, initialize the environment in which the kernel thread runs.
  • But it’s the jumpstart_eipWhere the original kernel_thread runtime function is replacedswitch_to_user_modeFunction, which begins the process of simulating interrupt return, entersinterrupt stack, and finally jump to the user state (code + stack) to start running;

Prepare the user stack

The above preparation of kernel stack is completed, so that it can jump into user code + stack in the form of interrupt return. However, our User Stack is not ready yet, and this area also needs to be initialized simply.

First we need to specify the location of the User Stack, which is typically located at the top of the 3GB space:

The location of the User Stack is supposed to be managed by the Thread’s process, but we haven’t started building process-related content yet, so as a test, we can arbitrarily specify the location of the User Stack for now. In the actual create_new_user_thread function, the parameter process is passed to specify under which process the thread should be created, Process assigns the user thread a stack position in the user space.

tcb_t* create_new_user_thread(pcb_t* process,
                              char* name,
                              void* user_function,
                              uint32 argc,
                              char** argv);

In this way, the user stack of multiple threads under the same process is roughly arranged like this, and there can be no overlap:

Once we have the location of the user stack, we can initialize the stack. The user thread runs essentially as a function call, so there is nothing special about its stack initialization except to build a stack of function calls. The stack consists of two parts:

  • parameter
  • The return address

Let’s initialize these two parts.

Copy the parameter

The arguments are in the create_new_user_thread function on the passed argc and argv. But we need to copy them onto the user stack so that user_function can run with them as arguments, which is what our normal C program’s main function looks like:

int main(int argc, char** argv);

The main function is the main thread of the process. If you create a new thread in the process, you will also have a similar form, such as the common pthread library, which involves passing the thread function and parameters:

int pthread_create(pthread_t *thread,
                   pthread_attr_t *attr,
                   void *(*start_routine)(void *),
                   void *arg);

The process of copying parameters is mainly implemented in the function prepare_user_stack. This involves building the argument argv, which is an array of strings, so we copy all the strings in argv to the top of the User Stack and write down their starting addresses to form a char* array, and then have argv refer to that array. The relationship between the Pointers is a little bit tricky. You can see it in the following picture:

Return from thread end

This leaves a ret addr, which is the return address of the Thread after it finishes.

Here we need to ask ourselves a question, after a thread ends, what should we do? The CPU instruction stream must of course continue to flow. It cannot stop there, nor can it run away. When a thread worker returns, it must be redirected to a place where the kernel collects the thread for the last time, and the thread’s life cycle ends. The scheduler then schedules the next thread to run.

Kernel_thread is a kernel thread that has a common exit mechanism:

void kernel_thread(thread_func* function) {
  function();
  schedule_thread_exit();
}

Schedule_thread_exit is the exit mechanism for a thread that ends. Instead of returning, the schedule_thread_exit enters the kernel’s closure and collection process. The scheduler will call the scheduler service. When the scheduler finds that it is TASK_DEAD, it will clean it up and schedule the next thread to run.

So can we just set the thread return address on the user stack to schedule_thread_exit? The answer is wrong.

Because schedule_thread_exit is kernel code, it cannot be called directly in user mode, otherwise a segment error will occur. Code segment size of user space is limited to less than 3GB, and the privileged CPL is 3. It is not possible to call kernel code above 3GB with DPL 0 (you may need to review the segment again).

So how do you go from user state to kernel state and finally call the schedule_thread_exit function? The answer is an interrupt, or, more accurately, a system call. The system call will be covered in more detail in a future article, but it should be known that the thread terminates in user state by running a function that looks something like this:

void user_thread_exit() {
  // This is a system call.
  thread_exit();
}

The system call to thread_exit leads us into kernel mode and eventually to the schedule_thread_exit function to execute the thread to finish the cleanup.

This looks perfect, but it brings up a new problem. The user_thread_exit function above is only what we assume, or expect. In fact, the user’s program code is written by the user himself, and then loaded from the disk to run. It is impossible for the kernel to know whether there is really such a function in it. The paradox is that the kernel will never be able to set up a valid user_thread_exit function for the ret addr of the user thread that can be called in user state.

I haven’t done much research on this either, and I don’t know what the standard solution is. This means that the user thread’s worker function never returns. Instead, it is encapsulated in a function similar to kernel_thread, such as user_thread:

Void user_thread(thread_func* function, int argc, void** argv) {function(argc, argv); thread_exit(); }

In fact, we can’t force users to create user threads according to this specification. Therefore, the creation of user threads should not let users directly operate the underlying system calls, but should be encapsulated by the corresponding specification library functions, such as pthread, and then the user calls these library functions. Perform operations related to Thread. In these library functions, they encapsulate the worker functions and arguments passed by the user into a conforming user thread function such as user_thread, and then invoke the system call provided by the OS to create the thread.

As for main, which is also a thread, its exit mechanism is easier to solve. Similarly, main must be wrapped in a function as well:

void _start(int argc, void** argv) {
  main(argc, argv);
  thread_exit();
}

The _start function is the wrapper on top of this and is actually the entry function to the actual user program. It should theoretically be provided by the standard library. When the C program is linked, it is linked in and set to the ELF executable’s entry address.

Set the TSS

The User thread is initialized and finished. Everything looks like it’s ready, but there’s still a hole left to fill. If the user thread never interrupts, the CPU will automatically enter the kernel stack to handle the interruption. (Of course, if the user thread never interrupts, there is no need for this, but this is not possible.) Most typically, clock interruptions occur continuously, and page faults are inevitable.

This jump from user to kernel is done automatically by the CPU and is determined by the hardware. How does the CPU know where the thread kernel stack is?

The answer is TSS (Task State Segment), which is really long and tedious and I don’t want to dwell on it here. Set this structure to the GDT and the thread’s kernel stack to its ESP0 field. Each time the CPU falls into the kernel state, it will find the TSS structure and use the ESP0 field. Locate the position of kernel stack.

  • tssInitialize the associated code inwrite_tssThis function;
  • Remember that each time the Thread switches, the Scheduler needs to update the TSSesp0Field to point to the top of the kernel stack for the new Thread (high address) :
void update_tss_esp(uint32 esp) {
  tss_entry.esp0 = esp;
}

void do_context_switch() {
  // ...
  update_tss_esp(next_thread->kernel_stack + KERNEL_STACK_SIZE);
  // ...
}

conclusion

This post is a bit more complicated and is the last one on Thread. It covers a wide range of topics. It may be necessary to review segments, interrupts, and the kernel thread creation + start process to string them together. After this, you should have a good understanding of how Thread works in the OS, including the following key points:

  • User and kernel thread/stack relationships, and their respective roles;
  • How user and kernel transitions occur and return, and how code + stack jumps;
  • The structure diagram of the kernel stack during thread startup, interrupt occurrence, processing and return, context switch, and its role;

In the next article, we will define the concept of process based on Thread.