Geekly Articles each Day
📜 ⬆️ ⬇️

Operating systems from scratch; level 3 (younger half)


In this lab, we will implement the ability to run custom programs. Those. processes and all dependent infrastructure. In the beginning we will figure out how to switch from privileged code, how to switch process contexts. Then we implement a simple round-robin scheduler, system calls and virtual memory management. In the end, we will derive our shell from kernel space to user space.


original


Null lab


First Laba: the younger half and the older half


The second laba: the younger half and the older half


Utility



Phase 0: Getting Started


As in the previous parts, for guaranteed work it is required:



Getting the code


In the 3-spawn turnip, there is nothing but questions, but no one interferes with stealing:


 git clone https://web.stanford.edu/class/cs140e/assignments/3-spawn/skeleton.git 3-spawn

After that, when it’s useless, the directory structure should look something like this:


 cs140e ├── 0-blinky ├── 1-shell ├── 2-fs ├── 3-spawn └── os

But inside the os -repy it will still be necessary to switch to the 3-spawn branch:


 cd os git fetch git checkout 3-spawn git merge 2-fs

Most likely you will again see merge conflicts. Something like this:


 Auto-merging kernel/src/kmain.rs CONFLICT (content): Merge conflict in kernel/src/kmain.rs Automatic merge failed; fix conflicts and then commit the result.

Conflicts of merge need to be resolved manually by changing the file kmain.rs . In doing so, you need to make sure that you saved all your changes from labs 2. After the conflicts have been resolved, add the git add files and commit it all. In order to get more information on this topic - see the tutorial on githowto.com .


ARM Documentation


In this task, we will constantly refer to three official documents on ARM. These three:


  1. ARMv8 Reference Manual
    This is the official ARMv8 architecture reference manual. A complete guide that covers the entire architecture. For the concrete implementation of this architecture in the process, we will need manual # 2. We will refer to sections of this large manual on ARMv8 by means of notes of the form ( ref : C5.2). In this case, this means that you need to look at the ARMv8 Reference Manual in section C5.2.
  2. ARM Cortex-A53 Manual
    This is a manual for a very specific implementation of ARMv8 (v8.0-A), which is used in Malinka. This manual will be referred to as notes of the form ( A53 : 4.3.30).
  3. ARMv8-A Programmer Guide
    Now we have a fairly high-level programming manual ARMv8-A. We will refer to it as notes ( guide : 10.1)

I highly recommend that you download these manuals to your disk. So it will be easier to open them every time. Especially the first because it is very, very large. By the way about this.


How do you even read this? We do not need to read it completely. Therefore, it is extremely important to start to know what we want to find in this manual. This manual has a good fit structure. It is divided into several parts. We are interested in AArch64 and are not interested in too deep immersion (we are not processor manufacturers). So we are not interested in many chapters from the word at all. In fact, parts of A, B and some information from C and D are enough for us. In the first two parts, the general concepts are described as applied to architecture and to AArch64 in particular. Part C describes the instruction set. We will use this part as reference for the most basic instructions and registers (for example, SIMD does not interest us now). Part D describes some details of the AArch64. In particular, about interrupts and all that.


Phase 1: ARM and a Leg (Hand and foot)


In this phase, we will study the ARMv8 architecture, switch to a less privileged level, tweak processor exception vectors, handle timer interrupts and breakpoints interrupt. Examine the exception levels in the ARM architecture. We are mainly interested in how to catch these exceptions and interrupts.


Subphase A: ARMv8 Overview


In this subphase, we will study the architecture of ARMv8. Here we will not write any code, but there are questions for self-examination.


ARM (Acron RISC Machine) is a microprocessor architecture with more than 30 years of history. Currently there are eight versions of this architecture. The latest ARMv8 was introduced in 2011. The Broadcom BCM2837 chip contains the ARM Cortex-A53 cores, which are ARMv8.0 based cores. Cortex-A53 (and the like) is an implementation of the architecture. And this is the realization that we will study in this whole part.


ARM microprocessors dominate the mobile market.

ARM is approximately 95% of the global smartphone market and 100% of the flagship smartphones. Including Apple iPhone or Google Pixel.

So far, we have tried to avoid issues related to the processor architecture. Rust did everything for us. In order to work with us in usspaces, we will need to carry out a certain amount of work at a low level. Programming directly proceeds will require familiarization with the assembler of this architecture and with all related concepts around it. We'll start with an overview of the architecture and deal with the most basic assembler instructions.


Registers


The ARMv8 architecture has the following registers ( ref : D1.2.1):



There are many more special-purpose registers . We will talk about them a bit later.


PSTATE


At any time, the percent ARMv8 allows you to access the program status through a pseudo-register named PSTATE ( ref : D1.7). This is not an ordinary case. It cannot be read or written to it directly. Instead, there are several special-purpose registers that can be used to operate on parts of the PSTATE pseudo-register. On ARMv8.0 this is:



Similar registers belong to the class of system or special registers ( ref : C5.2). Regular registers can be read from RAM with ldr or written to memory with str . System registers cannot be used this way. Instead, you need to use special commands mrs and msr ( ref : C6.2.162 - C6.2.164). For example, in order to read the NZCV in x1 we should use the following entry:


 mrs x1, NZCV

Execution status


At any point in time, ARMv8 percent is executed with a certain execution state. In total, there are exactly two such states. AArch32 - compatibility mode with 32-bit ARMv7. And AArch64 - 64-bit ARMv8 mode ( guide : 3.1). We will only work with AArch64.


Safe mode


At any given time, our percents are executed with a certain security state (guide: 3). This garbage can also be searched for in security mode or security world. Only two states: secure and non-secure . Those. safe and ordinary. We will work entirely as usual.


Exception levels


Besides, there are also exception levels ( guide : 3). Each level of exceptions corresponds to a certain level of privilege. The higher the level of exceptions, the more privileges the program starts at this level. There are 4 levels in total:



The Raspberry Pi processor is loaded into EL3. At this stage, the firmware is launched, provided by the Raspberry Pi foundation. The firmware switches the processor to EL2 and runs our kernel8.img kernel8.img . Thus, our core starts from EL2. A little later, we will switch from EL2 to EL1, so that our core works at the appropriate level of exceptions.


ELx registers


A number of system registers, such as ELR , SPSR and SP , are duplicated for each exception level. At the same time, the suffix _ELn is put to their names, where n is the level of exceptions to which this register belongs. For example, ELR_EL1 is the exception reference register for EL1, and ELR_EL2 is the same, but for EL2.


We will use the x suffix (for example in ELR_ELx ) when we need to refer to a register from the target exception level x . The target exception level is the exception level to which the CPU switches (if necessary) when the exception vector is triggered.


We will use the suffix s (for example, in SP_ELs , when you need to refer to the register in the original exception level s . The original exception level is the exception level at which the CPU was executed before the exception occurred.


Switch between exception levels


There is exactly one mechanism for increasing the level of exclusion and exactly one mechanism for reducing the level of exclusion.


To switch from a higher level to a lower level (privilege reduction), the running program must perform a return (return) from this level of elimination using the eret ( ref : D1.11). When executing the eret for an ELx processor level:



The SPSR_ELx register ( ref : C5.2.18), besides, contains the level of exceptions to which it is necessary to go. In addition, you should pay attention to the following additional effects of changing the levels of exceptions:



The transition from a lower level to a higher one occurs only as a result of an exception ( guide : 10). If not configured otherwise, the percents will intercept the exceptions for the next level. For example, if an interrupt is received while running in EL0, then the percent will switch to EL1 to handle the exception. When switching to ELx percent will do the following:



Please note that the exception syndrome register is valid only for synchronous exceptions. All general registers and SIMD / FP registers will contain the values ​​that they had when an exception occurred.


Exception vectors


When exceptions occur, the CPU transfers control to the place where the exception vector is located ( ref : D1.10.2). There are 4 types of exceptions, each of which contains 4 possible sources of exceptions. Those. total 16 exception vectors. Here are four types of exceptions:



Here are four interrupt sources:



From the description of the manual ( guide : 10.4):


When an exception occurs, the processor must execute the handler code that corresponds to the exception. The memory location where the handler [exceptions] is stored is called the exception vector. In the ARM architecture, exception vectors are stored in a table called the exception vector table. Each exception level has its own vector table, that is, for each of EL3, EL2, and EL1. The table contains instructions for execution, not a set of addresses [as in x86]. Each record in the vector table has a size of 16 instructions. Vectors for individual exceptions are arranged with fixed offsets from the beginning of the table. The virtual address of each table is based on the [special] vector address registers VBAR_EL3 , VBAR_EL2 and VBAR_EL1 .

These vectors are physically located in memory as follows:


Current exception level with SP = SP_EL0


Offset from VBAR_ELxAn exception
0x000Synchronized exception
0x080IRQ
0x100FIQ
0x180Seror

The current level of exceptions when SP = SP_ELx


Offset from VBAR_ELxAn exception
0x200Synchronized exception
0x280IRQ
0x300FIQ
0x380Seror

Lower level exceptions at which AArch64 is running


Offset from VBAR_ELxAn exception
0x400Synchronized exception
0x480IRQ
0x500FIQ
0x580Seror

Lower level exceptions at which AArch32 is running


Offset from VBAR_ELxAn exception
0x600Synchronized exception
0x680IRQ
0x700FIQ
0x780Seror

Summary


Currently, this is all we need to know about the ARMv8 architecture. Before continuing, try to answer these questions. For self test.


What are the aliases for register x30 ? [arm-x30]

If we write 0xFFFF to the x30 register, what other two names of this register can we use to retrieve this value?
')
How can I change the PC value to a specific address? [arm-pc]

How can I set the PC to address A using the ret instruction? How to set PC to address A using eret instruction? Specify which registers you will change in order to achieve this.

How can I determine the current level of exceptions? [arm-el]

What specific instructions would you follow to determine the current level of exclusion?

How would you change the stack pointer to return an exception? [arm-sp-el]

The stack pointer of the running program is A at the time the exception occurred. After processing the exception, you want to go back to where the program was running, but you want to change the stack pointer to B How do you do this?

Which vector is used for system calls from a lower EL? [arm-svc]

The user process is performed on EL0. This process calls svc . What address will be transferred to management?

Which vector is used for interrupts from a lower EL? [arm-int]

The user process is performed on EL0. At this point, a timer interrupt occurs. What address will be transferred to management?

How can I enable IRQ exception handling? [arm-mask]

In which register, what values ​​need to be written in order to unlock IRQ interrupts?

How would you use eret to enable AArch32 mode? [arm-aarch32]

The source of the exception is AArch64. The handler for this exception is also on AArch64. What values ​​in which registers would you change so that when returning from an exception via eret percent switches to the AArch32 execution mode?
Hint : Watch ( guide : 10.1)

Subphase B: Assembly instructions



In this subphase, we will explore the most basic commands from the ARMv8 command set. We will not write the code right now, but there are a couple of questions for self-testing.


Memory access


ARMv8 is a set of RISC download / storage instructions (a computer with a reduced instruction set). The defining feature of such a set of commands can be called the small fact that memory access can only be done through clearly defined instructions. In particular, the memory can only be read by reading into the register by the loading instruction, and it can only be written by the save instruction.


There are many instructions for loading / unloading (load / store) in different variations (for the most part they are of the same type). Let's start with the simplest form:



The <rb> register is called the base register . For example, if r3 = 0x1234 , then:


 ldr r0, [r3] // r0 = *r3 ( , r0 = *(0x1234)) str r0, [r3] // *r3 = r0 ( , *(0x1234) = r0)

In addition, you can add an offset from the interval [-256, 255] :


 ldr r0, [r3, #64] // r0 = *(r3 + 64) str r0, [r3, #-12] // *(r3 - 12) = r0

You can also specify a post index that changes the value in the base register after applying the load or saving:


 ldr r0, [r3], #30 // r0 = *r3; r3 += 30 str r0, [r3], #-12 // *r3 = r0; r3 -= 12

Or pre-index, which will change the value in the base register before applying the load or save:


 ldr r0, [r3, #30]! // r3 += 30; r0 = *r3 str r0, [r3, #-12]! // r3 -= 12; *r3 = r0

Offset, post-index and pre-index, they are known as addressing modes .


In addition, there is another command that can load / unload two registers at once. ldp and stp instructions (load pair, store pair). These instructions can be used with the same addressing modes as ldr and str .


 //  `x0`  `x1`  .     : // // |------| <x ( SP) // | x1 | // |------| // | x0 | // |------| <- SP // stp x0, x1, [SP, #-16]! //  `x0`  `x1`  .     : // // |------| <- SP // | x1 | // |------| // | x0 | // |------| <x (original SP) // ldp x0, x1, [SP], #16 //       ,     sub SP, SP, #16 stp x0, x1, [SP] ldp x0, x1, [SP] add SP, SP, #16 //   ,      x0, x1, x2,  x3. sub SP, SP, #32 stp x0, x1, [SP] stp x2, x3, [SP, #16] ldp x0, x1, [SP] ldp x2, x3, [SP, #16] add SP, SP, #32

Direct loading of values


The immediate (immediate) value is another name for an integer whose value is known without any computation. In order to load (for example) the 16-bit immediate into the register, optionally moving it a certain number of bits to the left, we need the command mov (move). In order to load the same 16 bits with a shift, but without replacing the other bits, we need movk (move / keep). Here is an example of using all of this:


 mov x0, #0xABCD, LSL #32 // x0 = 0xABCD00000000 mov x0, #0x1234, LSL #16 // x0 = 0x12340000 mov x1, #0xBEEF // x1 = 0xBEEF movk x1, #0xDEAD, LSL #16 // x1 = 0xDEADBEEF movk x1, #0xF00D, LSL #32 // x1 = 0xF00DDEADBEEF movk x1, #0xFEED, LSL #48 // x1 = 0xFEEDF00DDEADBEEF

Please note that the values ​​themselves are prefixed with # . LSL at the same time means a shift to the left.


Only 16 bits can be loaded into the register with an optional offset. By the way, the assembler can in many cases determine the necessary shift itself. mov x12, #(1 << 21) mov x12, 0x20, LSL #16 .



<label>: :


 add_30: add x1, x1, #10 add x1, x1, #20

, , adr ldr :


 adr x0, add_30 // x0 =     add_30 ldr x0, =add_30 // x0 =     add_30

ldr . adr .



, , mov :


 mov x13, #23 // x13 = 23 mov sp, x13 // sp = 23, x13 = 23


ELR_EL1 / mrs msr .


, - msr :


 msr ELR_EL1, x1 // ELR_EL1 = x1

- mrs :


 mrs x0, CurrentEL // x0 = CurrentEL


add sub :


 add <dest> <a> <b> // dest = a + b sub <dest> <a> <b> // dest = a - b

For example:


 mov x2, #24 mov x3, #36 add x1, x2, x3 // x1 = 24 + 36 = 60 sub x4, x3, x2 // x4 = 36 - 24 = 12

<b> :


 sub sp, sp, #120 // sp -= 120 add x3, x1, #120 // x3 = x1 + 120 add x3, x3, #88 // x3 += 88


and orr AND OR . add sub :


 mov x1, 0b11001 mov x2, 0b10101 and x3, x1, x2 // x3 = x1 & x2 = 0b10001 orr x3, x1, x2 // x3 = x1 | x2 = 0b11101 orr x1, x1, x2 // x1 |= x2 and x2, x2, x1 // x2 &= x1 and x1, x1, #0b110 // x1 &= 0b110 orr x1, x1, #0b101 // x1 |= 0b101


(Branching) — . PC . , b :


 b label // jump to label

( lr ), bl . ret lr :


 my_function: add x0, x0, x1 ret mov x0, #4 mov x1, #30 bl my_function // lr =   `mov x3, x0` mov x3, x0 // x3 = x0 = 4 + 30 = 34

br blr b bl , , :


 ldr x0, =label blr x0 //  bl label br x0 //  b label


cmp . , bne (branch not equal), beq (branch if equal), blt (branch if less than) .. ( ref : C1.2.4)


 //  1  x0   ,      x1, //   `function_when_eq`,   not_equal: add x0, x0, #1 cmp x0, x1 bne not_equal bl function_when_eq exit: ... //   x0 == x1 function_when_eq: ret

:


 cmp x1, #0 beq x1_is_eq_to_zero

: , .



ARMv8 . , . ( ref : C1.2.4). . ISA- Griffin Dietz. , :


memcpy ARMv8? [arm-memcpy]

, x0 , , x1 , x2 ( 8 ). memcpy ? , ret
: 6-7 .

0xABCDE ELR_EL1 ? [arm-movk]

, EL1 , 0xABCDE ELR_EL1 ARMv8?
: .

cbz ? [arm-cbz]

cbz ( ref : C6.2.36). ? ?

init.S ? [asm-init]

os/kernel/ext/init.S — , . _start 0x80000 . , EL1 .

os/kernel/ext/init.S context_save . , , - , , . (“read cpu affinity”, “core affinity != 0”) - :

MPIDR_EL1 ( ref : D7.2.74) ( Aff0 ), , . — setup . wfe .
: / , .

C: EL1


EL2 EL1. os/kernel/ext/init.S os/kernel/src/kmain.rs . , .



aarch64 ( os/kernel/src/aarch64.rs ), . sp() . current_el() , . , EL2 . , kmain() . , current_el() unsafe . , , EL1.


Switching


, EL1. os/kernel/ext/init.S :


 // FIXME: Return to EL1 at `set_stack`.

:


 mov x2, #0x3c5 msr SPSR_EL2, x2

, . , , SPSR_EL2 eret .


, FIXME . , EL1 CPU set_stack , . . , — eret . , current_el() 1 .


: PC ?

D:


. , . , , brk #n . kernel/ext/init.S kernel/src/traps .


Overview


, 16 , 16 . init.S _vectors . , 16 , handle_exception Rust kernel/src/traps/mod.rs . handle_exception . , , .



handle_exception , Rust, , . , , info , esr tf , .


, ( 2 C Rust). , , , . — , :



AArch64 ( guide : 9) procedure call standard .
Rust- handle_exception , , .


Rust , ?

, . Rust . , Rust , extern . handle_exception extern , Rust .


, , with HANDLER(source, kind) , . HANDLER(a, b) "", , #define . Those. :


 _vectors: HANDLER(32, 39)

:


 _vectors: .align 7 stp lr, x0, [SP, #-16]! mov x0, #32 movk x0, #39, LSL #16 bl context_save ldp lr, x0, [SP], #16 eret

lr x0 x0 32- 16 source 16 kind . context_save , _vectors . , , lr x0 .


context_save . ret context_restore . context_save , Rust.


Syndrome


(, ), ( ESR_ELx ) ( ref : D1.10.4). kernel/src/traps/syndrome.rs . Syndrome -. , ESR_ELx Rust esr . Sydnrome::from(esr) , , .


Info


handle_exception Info . 16 : source kind . , 32- , HANDLE x0 . , HANDLE - , Info .


Implementation


. , — brk , .. . , , .


brk kmain . :


 unsafe { asm!("brk 2" :::: "volatile"); }

:


  1. _vectors HANDLE . , Info .
  2. handle_exception context_save .
    , / caller-saved . 5 9 . 0 tf . .
    . AArch64 , SP 16 , /. , .
  3. VBAR , :
     // FIXME: load `_vectors` addr into appropriate register (guide: 10.4)
  4. handle_exception , .
    handle_exception info esr , , . . , , , aarch64::nop() . , . .
  5. Syndrome::from() Fault::from() .
    . ( ref : D1.10.4, ref : Table D1-8) , . “ISS encoding description” , , . , brk 12 Syndrome::Brk(12) , svc 77 Syndrome::Svc(77) . , 32- , , .
  6. brk .
    Syndrome::from() handle_exception , brk . , . . , Syndrome::from() . ESR_ELx .
    exit . exit , . brk . shell() kmain loop { } , .

, brk 2 kmain Brk(2) , source, CurrentSpElx kind Synchronous . . exit , .


, , . , , svc 3 . , .


As soon as everything works as you expected, you are ready to move on to the next stage.



UPD : the next part

Source: https://habr.com/ru/post/353994/

More articles:


All Articles