Batch processing system

There are no bugs that can't be fixed, only systems that aren't understood

PA3 is a watershed moment for the entire PA series. Starting from PA3, the complexity of the system begins to rise gradually, More and more layers of abstraction will be added, the system will also start to become more complete, and the applications will become more realistic.

This means that the chain of bug propagation will become more complex, and debugging will increasingly test your understanding of the system's behavior. If you've been relying on others to fix bugs before, without understanding the details of the system during the debugging process, You will find that in PA3, the gap between you and those who are more knowledgeable is rapidly widening: They are becoming more and more proficient in mastering the entire system, while you feel more and more that you're struggling to make progress, For example, the lectures and code are becoming increasingly difficult to understand, and the bugs are becoming more mysterious.

There's only one way to mend the pen after the sheep are lost: You really can't be lazy anymore.

In PA2, we have already implemented a von Neumann computer system and have managed to run typing games and FCEUX on AM. With IOE, we can almost port various small games to run on AM. These small games runs on the computer in the following way: they monopolize the entire computer system. We can keep playing the typing game on NEMU, and when we don’t want to play anymore, we exit NEMU and then rerun FCEUX to play.

In fact, early computers worked like this: The system administrator would load a specific program (actually punch cards from ancient times) into the computer, and the computer would keep executing this program until the program ended or the administrator manually terminated it, then the administrator would manually load the next program. The programs back then were far from as cool as the Super Mario you play, mostly tasks like scientific calculations and physical modeling (such as ballistic trajectory calculations).

Later, people thought that having an administrator manually load new programs each time was too troublesome. Recalling the working method of the von Neumann computer, one of its features is: when the computer finishes executing one instruction, it automatically executes the next one. Similarly, can we let the administrator prepare a set of programs in advance, so that after the computer finishes executing one program, it automatically executes the next one?

This is the idea of a batch processing system. With the batch processing system, it can free up the administrators' hands. The key to the batch processing system is to have a background program that automatically loads a new foreground program for execution when one foreground program finishes execution.

Such a background program is actually an operating system. Yes, you heard it right. This background program, which seems to do nothing, is really an operating system! Speaking of operating systems, you might immediately think of Windows, whose installation packages are several GB in size. However, in reality, the earliest operating system put into use, GM-NAA I/O, was born in 1956. One of its main tasks was the aforementioned "automatic loading of new programs", which specifically required the implementation of the following two functions:

• After the user program finishes execution, it can jump to the operating system's code to continue execution
• The operating system can load a new user program to execute

What is an operating system? (Recommended to ponder in the second round)

This is a big question. We also encourage you to come back and re-examine it after completing the operating system course.

New Requirements from the Operating System

If we think carefully, we will find that the above two functions actually contain a new requirement: control flow switching between programs. We know that function calls generally occur within a program (except for dynamically linked libraries), which belongs to the internal control flow of the program and can be implemented using the call/jal instructions. However, the above two requirements need to switch the control flow between the operating system and user programs. Nevertheless, the essence of control flow switching is just modifying the PC from one value to another (this is how hackers understand it). So, can we also use the call/jal instructions to implement control flow switching between programs?

Perhaps in the era when GM-NAA I/O was born, people might have actually done it this way: the operating system was a library function, and when the user program exited, it just needed to call this special library function, just like how we call halt() in our AM programs. However, later on, people gradually realized that the operating system is still quite different from other user programs: if a user program goes wrong, the operating system can run the next user program; but if the operating system crashes, the entire computer system will be unable to work. Therefore, people still hope to protect the operating system and ensure that it can work correctly as much as possible.

Faced with this requirement, using call/jal instructions to switch between the operating system and user processes seems too casual. The essence of an operating system is also a program, composed of functions, but regardless of whether the user program is unintentional or intentional, we do not want it to be able to switch the control flow to any function in the operating system. What we hope for is a way to switch the control flow with restricted entry points, which obviously cannot be achieved through program code.

A Strict Hierarchical System

In order to prevent programs from switching the execution flow to arbitrary locations in the operating system, hardware gradually introduced protection mechanisms and related features. For example, the i386 introduced the concepts of protected mode and privilege levels, while the mips32 processor can run in kernel mode and user mode, and riscv32 has machine mode (M-mode), supervisor mode (S-mode), and user mode (U-mode). The ideas behind these concepts are similar: only programs with higher privilege levels can perform certain system-level operations. If a program with a lower privilege level attempts to perform an operation that it does not have permission to execute, the CPU will throw an exception signal to prevent this illegal behavior from occurring. Generally speaking, the most suitable role for a system administrator is the operating system itself, which has the highest privilege level and can perform all operations. Unless specifically allowed, user programs running on the operating system generally have the lowest privilege level. If they attempt to disrupt social harmony, they will be sentenced to "death".

Taking RISC-V processors that support modern operating systems as an example, they have three privilege modes: M, S, and U, representing machine mode, supervisor mode, and user mode, respectively. M mode has the highest privilege level, while U mode has the lowest. Resources that can be accessed by lower privilege levels can also be accessed by higher privilege levels. So how does the CPU determine whether a process has executed an unauthorized operation? The answer is simple. It only needs to maintain a register in hardware to identify the current privilege mode (which is part of the computer's state), and then check the current privilege mode when accessing resources that can only be accessed by higher privilege levels. For example, RISC-V has a privileged instruction sfence.vma, and the manual requires that it can only be executed when the processor's current privilege mode is not lower than S mode. Therefore, we can add some simple logic in hardware to implement the privilege mode check:

is_sfence_vma_ok = (priv_mode == M_MODE) || (priv_mode == S_MODE);

As we can see, the privilege mode check is nothing more than some gate circuits. If the check fails, this operation will be judged as an illegal operation. The CPU will throw an exception signal and jump to a memory location agreed upon with the operating system, handing it over to the operating system for subsequent processing.

Typically, the operating system runs in S mode, so it has permission to access all code and data. On the other hand, ordinary programs run in U mode, which means they can only access code and data in U mode. This way, as long as the operating system puts its private code and data in S mode, malicious programs will never be able to access them.

Similarly, the operating system on x86 runs in ring 0, while user processes run in ring 3. On mips32, the operating system runs in kernel mode, and user processes run in user mode. These protection-related concepts and check processes are all implemented through hardware. As long as software runs on top of hardware, it cannot escape this net. The hardware protection mechanism ensures that malicious programs can never get away unscathed, making a huge contribution to building a harmonious computer society.

What a wonderful feature! Unfortunately, many of the concepts mentioned above are just briefly touched upon, and a real protection mechanism still needs to consider more details. ISA manuals generally have a dedicated chapter to describe the protection mechanism, which shows that the protection mechanism is not just a simple matter of talking about it. According to the KISS principle, we do not intend to add a protection mechanism in NEMU. We let all user processes run at the highest privilege level. Although all user processes have permission to execute all instructions, since the user programs in PA are all written by ourselves, everything is still within our control. After all, we have already grasped the essence of the protection mechanism from the story above: adding some gate circuits related to privilege level checks (such as comparator circuits) in the hardware. If an illegal operation is detected, it will throw an exception signal, causing the CPU to jump to an agreed-upon target location and perform subsequent processing.

The Disintegrating Order

Privilege level protection is a core mechanism of modern computer systems, but having this strict hierarchical system does not mean that we can rest easy. Hackers always rack their brains to probe the boundaries of this system. The most recent big events in the cybersecurity field are the two infamous hardware vulnerabilities, Meltdown and Spectre, which were exposed in January 2018. These two epic-level vulnerabilities shocked the world because they broke the boundaries of privilege levels: under certain conditions, malicious programs can steal information from the operating system at an extremely high rate. Intel's chips were pointed out to have the Meltdown vulnerability, while the Spectre vulnerability endangers chips of all architectures, with no exceptions. They can be said to be the two most impactful vulnerabilities in the history of computer architecture so far. If you execute cat /proc/cpuinfo, you may see the shadow of these two vulnerabilities in the bugs information.

Meltdown and Spectre sounded the alarm for those chip designers who had been blindly pursuing performance in the past: without security, no matter how fast the chip runs, it is in vain. Interestingly, the ones who directly paid for this farce were the engineers of major cloud computing platforms: in the week when the vulnerabilities were exposed, engineers from Alibaba Cloud and Microsoft Azure worked overtime for several consecutive nights, trying every means to patch the cloud platforms to prevent customers' data from being maliciously stolen.

However, as a teaching experiment, the topic of security is still too far away from PA, and even performance is not the main goal of PA. The point of this example is that real computer systems are very complex and far from perfect. The emergence of these vulnerabilities also indicates to a certain extent that people can no longer fully understand the mutual influence between each module all at once. But the principles behind computers are all inherited from the same origin. Understanding these principles in a small and refined teaching system, and then understanding and improving real systems, is also a valuable gain from doing PA.