?? Computers have become the daily work of modern people 、 An indispensable tool in study and life . The operating system is the soul of the computer , As an interface for users to use computers , It is responsible for scheduling the execution of various user programs , To enable a computer to perform a specific task ; As the manager of computer hardware resources , It is responsible for coordinating all kinds of equipment in the computer to work efficiently . The importance of operating systems is self-evident .
For software engineers , Understanding the working principles and key mechanisms of the operating system is the prerequisite for designing high-quality applications , But it's very difficult to do that .
One side , Operating system design involves all aspects of computer science and engineering , Including data structure and algorithm 、 Computer composition and system structure 、 computer network , Even the core knowledge of programming language and compiler system , And concurrency 、 Core concepts like synchronization and communication .
On the other hand , As a complex and huge software product , Understanding the operating system requires a deep combination of theory and practice .
There are plenty of learning materials about the operating system . There are those who expound the basic principles , There are those who analyze typical systems , There are also those who construct the example system ; There are professional theorists , There are also application-oriented practitioners . There are many angles , The content is simple and complex .
? The greatest feature of this book is that the author combines his many years of Linux Practical teaching experience of operating system . As an experienced senior software engineer and professional teacher , The author of this book is based on his own study and research Linux What I learned , Innovatively with a mykernel and MenuOS Teaching and experimental organization for basic experimental platform , It realizes the natural integration of theoretical study and engineering practice , It has achieved twice the result with half the effort .
meanwhile , The book designs a wealth of unit tests and experiments , Guide readers to master the knowledge step by step , And effectively promote readers to think deeply and practice what they have learned .
Based on the operating system course offered by the author in this book , Its teaching form involves face-to-face classroom teaching and online MOOCS teaching , Course selection includes both master of software engineering , It also includes general engineering practitioners , The number of students has reached tens of thousands . The publication of this book reflects the author's serious absorption of a large number of students' feedback , Constantly optimize the teaching content of the course and the results of process organization .
This paper focuses on the working principle of computer , Specifically, it involves the working model of stored program computer 、 Basic assembly language , as well as C How can the assembly code assembled by language program be executed step by step on the working model of stored program computer . It focuses on the function call stack related assembly instructions , Such as call/ret and pushl/popl.
Stored program computer working model
The concept of stored program computer is simple , But it's revolutionary in the history of computers , So far, it is still a very meaningful invention in the history of computer development . A computer or smartphone with limited hardware can install all kinds of software , Perform a variety of procedures , This seems to be taken for granted by people , In fact, it is the credit of stored program computer .
The main idea of stored program computer is to store program in computer memory , Then execute the first instruction of the program according to the first address of the stored program in the memory , In the future, it will be executed according to the instructions written in the program , Until the end of program execution .
I believe many people, especially those majoring in computer science, have heard of Turing machine and Feng · The Neumann machine . Turing is concerned with the philosophical definition of computing , It's a virtual abstract machine , It's the first description of a modern computer . Just provide the right procedure , A Turing machine can do any operation . Computers built on Turing machines store data in memory , The logic of the program is embedded in the hardware .
Unlike Turing machines , feng · The Neumann machine is a practical architecture , We call it Feng · Neumann architecture , It is still the foundation of almost all computer platforms . We all know “ Dismember an ox as skillfully as a butcher ” This idiom , After repeated practice , Master the objective laws of things , Do things with ease , handle very skillfully . feng · Neumann architecture is one that all kinds of computer architectures need to comply with “ Objective laws ”, Understanding it is very important to understand computers and operating systems . below , Let's see what Feng is · Neumann architecture .
stay 1944～1945 During the year , feng · Neumann points out that programs and data are logically the same , Programs can also be stored in memory . feng · The key points of Neumann architecture include ：
feng · The Neumann architecture is shown in the figure 1-1 Shown , Where the arithmetic unit 、 Memory 、 controller 、 Input devices and output devices 5 The big basic types of components make up the computer hardware ;
chart 1-1 feng · Neumann architecture
Binary system is used to represent instruction and data in computer ;
Store the program and data in the memory first , Then start the computer to work , That's the basic meaning of stored programs .
The basis of computer hardware is CPU, It works with memory and input / Output （I/O） The device interacts , Receiving data from an input device , Send data to the output device .
CPU By solver （ Arithmetic logic unit ALU）、 The controller consists of some registers . There is a very important register called the program counter , stay IA32（x86-32） Medium is EIP, Indicates the address in memory of the next instruction to be executed .
C/C++ A programmer can translate EIP As a pointer , Because it always points to the address of an instruction .CPU It's from EIP Take an instruction from the address you pointed to , After the execution EIP It will automatically add one , Execute the next command , And then take the next instruction to execute ,CPU image “ snake ” It's always in memory “ eat ” Instructions .
CPU、 Memory and I/O Devices are connected by bus . Instructions and data are stored in memory .
“ Binary system is used to represent instruction and data in computer ” indicate , The functions and processing of instructions and data are different , But they can be stored in memory in binary form .
Above mentioned 3 The first point points out that Feng · The core of Neumann architecture is stored program computer .
We use the programmer's mind to abstract the stored program computer , Pictured 1-2 Shown .
chart 1-2 Schematic diagram of the working principle of stored program computer
We can CPU Abstract into a for loop , Because it's always executing next instruction（ Next order ）, And then take an instruction from memory to execute . From this point of view , Memory holds instructions and data ,CPU Responsible for interpreting and executing these instructions , They're connected by bus . The principle that a computer can execute programs automatically is revealed here .
There is a problem here ,CPU What kind of instructions can I identify , We need to have a definition here . Readers who have learned programming know it API, That's the API .
And for programmers , Another one is called ABI The interface of , It's mainly the coding of some instructions . In terms of instruction coding , We won't go into that specific detail , And it's only about assembly .
As for how these instructions are encoded into binary machine instructions , We don't have to care about , Interested readers can find information about instruction coding . Besides , These instructions involve some registers , These registers have some conventions , We agree what kind of instruction should use what register .
meanwhile , We also need to understand the register layout . also , Most instructions have direct access to memory , about x86-32 In terms of computer instruction set , It's also an important concept .
about x86-32 Computer , There is one EIP A register points to an instruction in memory ,EIP It's automatic plus one （ It's not a byte , Neither 32 position , It's about adding an order ）, although x86-32 Each instruction takes up different storage space in , But it can intelligently and automatically add to the next instruction , It can also be modified by other instructions , Such as call、ret、jmp etc. , These instructions correspond to C Function calls in language 、return and if else sentence .
Now the vast majority of computing devices , As small as smartphones , Big to supercomputers , The basic core part can use Feng · Neumann architecture （ Stored program computer ） To describe . therefore , Stored program computer is a very basic concept , It is the basis for us to understand the working principle of computer system .
x86-32 Assembly basis
Intel The processor family is also known as x86, Through constant development , Architecture has gone through 16 position 、32 Bit and 64 There are several key stages .32 Bit architecture is called IA32,64 Bit architecture is called x86-64, But to make a clear distinction between the two , In this book 32 Bit architecture is called x86-32. This book is related to Linux The kernel uses the same assembly format , use AT&T Assembly format .
1.x86-32 CPU The register of
For the convenience of the reader , Let's start with 16 Bit 8086 CPU The register of .8086 CPU In all 14 individual 16 Bit register ：AX、BX、CX、DX、SP、BP、SI、DI、IP、FLAG、CS、DS、SS and ES. this 14 Each register is divided into general registers 、 Control register and segment register 3 Types .
General purpose registers are divided into data registers 、 Pointer register and index register .
AX、BX、CX and DX Collectively referred to as data registers .
qAX（Accumulator）： Accumulation register , Also known as accumulator .
qBX（Base）： Base address register .
qCX（Count）： Counter register .
qDX（Data）： Data register .
SP and BP Collectively referred to as pointer registers .
qSP（Stack Pointer）： Stack pointer register .
qBP（Base Pointer）： Base pointer register .
SI and DI Collectively referred to as index registers .
qSI（Source Index）： Source index register .
qDI（Destination Index）： Destination address register .
The control register is mainly divided into instruction pointer register and flag register .
qIP（Instruction Pointer）： Instruction pointer register .
qFLAG： Flag register .
Segment registers are mainly code segment registers 、 Segment register 、 Stack segment register and additional segment register .
qCS（Code Segment）： Code segment register .
qDS（Data Segment）： Segment register .
qSS（Stack Segment）： Stack segment register .
qES（Extra Segment）： Additional segment register .
The above data register AX、BX、CX and DX Can be treated as two separate 8 Bit register , Pictured 1-3 Shown , With AX Register as an example .
chart 1-3 AX Register diagram
qAX Registers can be divided into two separate 8 Bit AH and AL register .
qBX Registers can be divided into two separate 8 Bit BH and BL register .
qCX Registers can be divided into two separate 8 Bit CH and CL register .
qDX Registers can be divided into two separate 8 Bit DH and DL register .
Except for the above 4 In addition to two data registers , None of the other registers can be divided into two independent 8 Bit register . Be careful , Each separate register has its own name , It can be accessed independently . Programmers can take advantage of this kind of data register “ Can be divided or combined ” Characteristics of , Handle words flexibly / Byte information .
I understand 16 Bit 8086 CPU After the register of , Let's see 32 Bit register .
IA32 The registers included include ：
q4 Data registers （EAX、EBX、ECX and EDX）.
q2 Index and pointer registers （ESI and EDI）.
q2 A pointer register （ESP and EBP）.
q6 Segment registers （ES、CS、SS、DS、FS and GS）.
q1 Instruction pointer registers （EIP）.
q1 Flag register （EFlags）.
32 The bit register just puts the corresponding 16 The bit register extends to 32 position , Pictured 1-4 As shown in the for EAX Register diagram , It adds a E. All begin with E The register of , It's usually 32 Bit .
EAX Accumulation register 、EBX Base register 、ECX Count register and EDX Data registers are general purpose registers , The programmer can define how to use them when he writes them .EBP Is the stack base pointer , More important ;ESI、EDI It's the index register ;ESP It's more important , It's the top of the stack register .
This may involve the concept of stack , Readers of data structure courses should know the concept of stack , I'll talk about it later in this book push Instruction stack pressing and pop Instructions are out of the stack , It is to press a data into a stack and eject a data from the stack . These are all 32 Bit general register .
chart 1-4 EAX Register diagram
It is worth noting that in 16 position CPU in ,AX、BX、CX and DX The address of the storage unit cannot be stored as a base address and an index register , But in 32 position CPU in ,32 Bit register EAX、EBX、ECX and EDX Not only can it transmit data 、 Save the results of arithmetic and logic operation , It can also be used as a pointer register , So these 32 Bit registers are more versatile .
In addition to general registers , There are also some segment registers . Although segment registers are rarely used in this book , But we still need to know . except CS、DS、ES and SS Outside , There are other additional segment registers FS and GS.
What is commonly used is CS Registers and SS register . Our instructions are stored in code segments , In locating an instruction , Use CS:EIP To pinpoint its address .
in other words , First, you need to know which code segment the code is in , Then you need to know the relative offset address of the instruction within the code segment EIP, It's usually used CS:EIP Accurately indicate the memory address of an instruction . And stack segments , Each process has its own stack segment （ stay Linux In the system , Each process has a kernel state stack and a user state stack ）.
The function details of flag register are complicated , This book will not introduce it carefully , Readers know that the flag register can save some of the current state .
Now most mainstream computers use 64 Bit CPU, Then we also need to have a brief understanding of x86-64 The register of . actually ,64 Bit and 32 The register of bits is not very different , It just comes from 32 Bits extend to 64 position . I'll take a “R” I mean 64 Bit register , Such as RAX、RBX、RCX、RDX、RBP、RSI、RSP, also Flags Change it to RFLAGS,EIP Change it to RIP.
in addition , More general registers have been added , Such as R8、R9 etc. , These additional general registers have different names from other general registers , In use, they all follow the rules of the caller , To put it simply, use it casually .
2. data format
stay Intel In the terminology specification of , The word means 16 Bit data type ; stay IA32 in ,32 The number of digits is called a double word ; stay x86-64 in ,64 The number of digits is called four words . chart 1-5 As shown in the for C The basic types of... In language IA32 Express , The assembly code suffixes listed in it are often seen in assembly code .
chart 1-5 C The basic types of... In language IA32 Express
3. Addressing methods and common assembly instructions
Assembly instructions contain operands and operands , The operands are divided into the following 3 Kind of ：
（1） An immediate number is a constant , Such as $8, use $ The beginning is followed by a number ;
（2） Number of registers , Represents a value stored in a register , Such as %eax; And for byte operations , yes 8 One of a single byte register , Such as %al（EAX Low in register 8 position ）;
（3） Memory reference , According to the calculated effective address to access a memory location .
There are also some common assembly instructions , Let's see how they work . The most common assembly instruction is mov Instructions ,movl Medium l Refer to 32 position ,movb Medium b Refer to 8 position ,movw Medium w Refer to 16 position ,movq Medium q Refer to 64 position . We use 32 I'll give you an introduction .
First, register addressing is introduced . Register addressing is to operate register , Not dealing with memory , Such as %eax, among % The beginning is followed by a register name .
The above code puts the register %eax Put the content of %edx in . If you think of the register name as C Variable names in language code , It's equivalent to ：
edx = eax;
Address immediately （immediate） Use one. $ The beginning is followed by a number . for example ：
movl $0x123, %edx
Is to put 0x123 This hexadecimal number goes directly to EDX In the register . If you think of the register name as C Variable names in language code , It's equivalent to ：
edx = 0x123;
Immediate addressing has nothing to do with memory .
Direct addressing （direct） It's just a number , Not at the beginning $ Symbol . At the beginning there is $ The numerical value of the sign means that this is an immediate number ; No, $ The symbol means that this is an address . for example ：
movl 0x123, %edx
It's the hexadecimal 0x123 The data stored in the memory that the memory address points to is put into EDX In the register , This is equivalent to C The language code ：
edx = *(int*)0x123;
hold 0x123 This number is forced into a 32 Bit int Pointer to a variable of type , With another * Take the value it points to , Then put EDX In the register , This is called direct addressing .
let me put it another way , It is to use memory address to access data in memory directly .
Indirect addressing is a register with parentheses . Illustrate with examples ,%ebx The value stored in this register is a memory address , Add a small bracket to indicate the data stored in this memory address , Let's put it in EDX In the register ：
move (%ebx), %edx
Equivalent to ：
edx = *(int*)ebx;
Put this EBX The value stored in the register is forced into a 32 Bit int Pointer to a variable of type , With another * Take the value it points to , Then put EDX In the register , This is called indirect addressing .
Index addressing is a little more complicated than indirect addressing . for example ：
movl 4(%ebx), %edx
Readers will find that in the code “（%ebx）” There's one ahead 4, That is, on the basis of indirect addressing , Add an immediate number to the original address 4, amount to ：
edx = *(int*)(ebx+4)
Put this EBX The value stored in the register plus 4, And then force it into a 32 Bit int Pointer to type , With another * Take the value it points to , Then put EDX In the register , This is called index addressing .
As mentioned above CPU How to operate registers and memory , It's all basic knowledge , It needs to be firmly grasped .
x86-32 Most of the instructions in have direct access to memory , But there are still some instructions that can operate directly on memory , Such as push/pop. They are based on ESP Register points to the memory location for stack pressing and stack out operation , Note that by default, a specific register is used during instruction execution .
What needs special explanation is , What is used in this book is AT&T Assembly format , This is also Linux The assembly format used by the kernel , And Intel The assembly format is slightly different .
When we search for information, we may encounter Intel Assembly code , Generally speaking , All capital letters are usually Intel assembly , All lowercase letters are usually AT&T assembly .
The register names used in the code in this book comply with AT&T The assembly format is all lowercase , Register names are usually capitalized in the text , Because they are acronyms .
There are also several important instructions ：pushl/popl and call/ret.pushl Express 32 Bit push, Such as ：
Is to put EAX The value of the register is pushed to the top of the stack . It actually does these two actions , The first one is ：
subl $4, %esp
Put the top of the stack ESP Register value minus 4. Because the stack is growing down , So with the minus instruction subl, That is to reserve a storage unit at the top of the stack . The second action is ：
movl %eax, (%esp)
hold ESP Register with a parenthesis （ Indirect addressing ）, Is to put EAX The value of the register is placed in ESP Where the register points to , At this time ESP The register already points to the reserved storage unit .
Next up popl Instructions , Such as ：
That is to take a storage unit from the top of the stack （32 Digit value ）, From the top of the stack to EAX In the register , This is called out of the stack . Out of stack also corresponds to two operations ：
movl (%esp), %eax
addl $4, %esp
The first step is to put the value at the top of the stack into EAX In the register , And then with instructions addl Add... To the top of the stack 4, It is equivalent to the stack retreating one storage location up , That is, the stack is shrinking . Every time an instruction is executed pushl Stacks are growing , Execution instruction popl The stacks are shrinking .
call Instructions are function calls , Call an address . for example ：
The above code actually does two actions , Here are two pseudo instructions , Be careful , There is no actual command for these two actions , We use it “（*）” Let's make a special mark , These two actions are done by hardware at one time . For security reasons ,EIP Registers cannot be used and modified directly .
pushl %eip (*)
movl $0x12345, %eip (*)
The above pseudo instruction first puts the current EIP Register stack , hold 0x12345 This immediate number is put in EIP In the register , This register is used to tell CPU The storage address of the next instruction .
Put the current EIP Register value stack is to save the address of the next instruction , And then to EIP A new value has been assigned to the register 0x12345, That is to say CPU The next instruction to execute is from 0x12345 Position .
Look again at the relationship between call The corresponding instruction ret,ret Instructions are functions that return , for example ：
The above code actually does an action , Here's a pseudo instruction , Be careful , There is no actual command for this action , We use it “（*）” Let's make a special mark , This action is done by hardware at one time . For security reasons ,EIP Registers cannot be used and modified directly .
That is, the current stack top of a storage unit （ It's usually by call The contents of instruction stack ） Put it in EIP In the register . Above pushl/popl and call/ret The actions corresponding to assembly instructions are summarized as shown in the figure 1-6 Shown .
chart 1-6 pushl/popl and call/ret Assembly instruction
To sum up ,call The instructions correspond to C In this language, we call a function , That is to say call The starting address of a function .ret Instruction is to call the function when the stack EIP Register value （ namely call The address of the next instruction of the instruction ） Restore to EIP In the register ,ret The next instruction after the instruction returns to the next instruction in the function call position .
In other words, the function call is over , Continue to execute the next instruction after the function call , This sum C The procedure of function call in language is strictly corresponding . But here's the thing , Take a “（*）” These instructions are not directly used by programmers , It's a pseudo instruction .
because EIP Registers cannot be modified directly by programmers , Only by special instructions （ Such as call、ret and jmp etc. ） Indirect modification .
If the programmer can modify it directly EIP register , Then there will be serious security risks . Readers can think about why ？ Let's not discuss .
4. Analysis of assembly code examples
We've got a general idea of instructions and registers , Let's do an exercise to verify our understanding . When the stack is empty , After executing the following assembly code fragment , What happened to the stack and registers ？
1 push $8
2 movl %esp, %ebp
3 subl $4, %esp
4 movl $8, (%esp)
We analyze what the assembly code does at every step . First, if the stack is empty ,EBP and ESP Registers point to the bottom of the stack .
The first 1 The line statement is to put the immediate number 8 Pressing stack （ That is, first ESP Register value minus 4, And then count it immediately 8 Put it at the top of the current stack ）.
The first 2 Line statements are ESP The value of the register is placed in EBP In the register , Is to put ESP The contents of the register are placed in EBP In the register , hold EBP The register also points to the current ESP The location that the register points to .
let me put it another way , A new logical empty stack is created in the stack , It's not easy to understand , It doesn't matter that readers can't understand it for the time being . There will be C Language programs are assembled into assembly code to analyze how function calls are implemented , It involves the function call stack framework .
The first 3 The instruction in the line statement is subl, It's a ESP The value stored in the register is subtracted from 4, in other words , Top pointer of stack ESP The register is moved down one storage location （4 Bytes ）.
The last line is to put the immediate number 8 Put it in ESP The memory address that the register points to , That is to say, the immediate number 8 Put it at the top of the stack by indirect addressing .
This example is about some operations of stack and register , We can compare the above text to explain the process of tracking the changes of stack and register step by step , In order to more accurately understand the role of instructions .
Let's take a look at the assembly code , Also, when the stack is empty , After executing the following assembly code fragment , What happened to the stack and registers ？
1 pushl $8
2 movl %esp, %ebp
3 pushl $8
Also, let's analyze what the assembly code does at each step . First, if the stack is empty EBP and ESP Registers point to the bottom of the stack .
The first 1 The line statement is to put the immediate number 8 Pressing stack , That is, the stack has one more storage unit and one immediate number 8, It also changed ESP register .
The first 2 The line statement puts ESP The value of the register is placed in EBP In the register , The stack space doesn't change , but EBP The register has changed .
The first 3 The line statement will immediately count 8 Pressing stack , That is, the stack has one more storage unit and one immediate number 8.
Readers will find that , The actual effect of this example is exactly the same as that of the previous one .
After a little trial , Let's look at the more complex assembly code below ：
1 pushl $8
2 movl %esp, %ebp
3 pushl %esp
4 pushl $8
5 addl $4, %esp
6 popl %esp
This piece of assembly code also starts when the stack is empty EBP and ESP Registers point to the bottom of the stack .
The first 1 The line statement is to put the immediate number 8 Pressing stack , That is, the stack has one more storage unit and saves the immediate number 8, It also changed ESP register .
The first 2 Line statements are ESP The value of the register is placed in EBP In the register , The stack space doesn't change , but EBP The register has changed .
The first 3 Line statements are ESP The contents of the register are stacked in the storage unit at the top of the stack . It should be noted that ,pushl The instructions themselves change ESP register .“pushl %esp” Statement is equivalent to the following two instructions ：
subl $4, %esp
movl %esp, (%esp)
obviously , In preservation ESP The value of the register changed before it was put on the stack ESP register , The data saved to the top of the stack should be current ESP Register value minus 4.ESP The value of the register has changed , At the same time, the stack space has one more storage unit to save the changed ESP Register value .
The first 4 The line statement is to put the immediate number 8 Pressing stack , That is, the stack has one more storage unit to store the immediate number 8, It also changed ESP register .
The first 5 Line statements are ESP Register value plus 4, This is equivalent to shrinking the stack space by one storage unit .
The last statement is equivalent to the following two instructions ：
movl (%esp), %esp
addl $4, %esp
That is to put the data at the top of the stack into ESP In the register , And then it will ESP Register plus 4. This piece of code is more complicated , because ESP Registers are used as operands , Has been pushl/popl Instructions are used and modified during execution .
Readers need to carefully analyze and think about the assembly code to understand the whole execution process , The rest of this book will be combined with C Code function calls and function returns , To further understand the assembly code involved in building a function call stack and dismantling a function call stack .
《 Dismember an ox as skillfully as a butcher Linux Kernel analysis 》
Meng Ning Lou Jiapeng Liu Yudong Writing
This book starts from understanding the core working mechanism of computer hardware （ Stored program computers and function call stacks ） And how user mode programs fall into the kernel through system calls （ Interrupt exception ） Starting with , Through up and down two-way attack strategy , And use the disassembly code of the actual runnable program to understand the operating system kernel from a practical point of view , Then start to analyze Linux Kernel source code , From system calls to the kernel , Process scheduling and process switching , Finally, return to the user mode process .