⬆️ ⬇️

Operating systems from scratch; level 1 (upper half)

It's time for the next part. This is the second half of the translation labs β„–1 . In this release we will write peripheral drivers (timer, GPIO, UART), we will implement the XMODEM protocol and one utility. Using all this we will write a command shell for our kernel and a bootloader that will allow us not to poke the microSD card back and forth.



The younger half .

Start reading is worth with zero labs .



Phase 3: Not a Seashell





This time we will write a couple of drivers for the integrated peripherals. We are interested in the built-in timer, GPIO and UART. They will be enough for us to write the built-in command line, and a little later it will come in handy for creating a bootloader (which will somewhat simplify further work).



What is a driver?



The term driver or device driver is software that directly interacts with a certain hardware device, controls it, etc. Drivers provide a higher level interface for the devices they control. Operating systems interact with device drivers to build an even higher level of abstraction over them (for the sake of convenience, of course!). For example, the Linux kernel provides ALSA (Advanced Linux Sound Architecture), an API for audio that interacts with drivers, which in turn communicate directly with sound cards.


Subphase A: Getting Started



In the rest of the assignment, we will work inside the turnip os , which will be used not only in this part, but throughout the rest of the course. It is this repository that will eventually become the operating system.



I recommend the following directory structure for the lab and everything else in relation to this course:



 cs140e β”œβ”€β”€ 0-blinky β”‚ β”œβ”€β”€ Makefile β”‚ β”œβ”€β”€ phase3 β”‚ └── phase4 β”œβ”€β”€ 1-shell β”‚ β”œβ”€β”€ ferris-wheel β”‚ β”œβ”€β”€ getting-started β”‚ β”œβ”€β”€ stack-vec β”‚ β”œβ”€β”€ ttywrite β”‚ β”œβ”€β”€ volatile β”‚ └── xmodem └── os β”œβ”€β”€ Makefile β”œβ”€β”€ bootloader β”œβ”€β”€ kernel β”œβ”€β”€ pi β”œβ”€β”€ std └── volatile 


Convenient and neat. 0-blinky and 1-shell belong to the previous and current labs, and you can get os here like this:



 git clone https://web.stanford.edu/class/cs140e/os.git os git checkout master 


Make sure everything is properly located and run make inside os/kernel . If all goes well, the command will succeed.



Project structure



The os directory contains the following set of subdirectories:





All driver code is in the pi library. pi uses the volatile library and (optionally) std . kernel and bootloader use pi to communicate with devices. And besides this depend on std . volatile does not depend on anything. Graphically, these relationships will look something like this:





Firmware



We need to update the firmware raspberry before continuing. You can download this all with the command make fetch from the os directory. It will load the necessary materials into the files/ daddy. Copy firmware/bootcode.bin , firmware/config.txt and firmware/start.elf to the root of the microSD card. You can copy act-led-blink.bin from the last part, rename to kernel8.img . So you can check that everything works. There should blink green LED on the very Malinka.



Updated volatile



This library from the os folder is slightly different from the code that was studied in phase 2. The changes make it a little easier to use this in the context of writing device drivers. The main differences are:



  1. UniqueVolatile replaced by Unique<Volatile>
  2. Added type Reserved , which can absolutely nothing and is used as a stub


There is another, more significant difference. All types from the library wrap T , not *mut T This allows us to use any raw addresses without wrapping them, but casting them like this: 0x1000 as *mut Volatile<T> . In addition, we can specify a structure containing fields wrapped in Volatile . Something like this:



 #[repr(C)] struct Registers { REG_A: Volatile<u32>, REG_B: Volatile<u8> } //    .  `Registers`   `0x4000`  . //     `u32`     `u8`      // (. ). let x: *mut Registers = 0x4000 as *mut Registers; //       `unsafe`. //   Rust        unsafe { //   Rust      (*x).REG_A.write(434); let val: u8 = (*x).REG_B.read(); } 


What is #[repr(C)] ?



The postscript #[repr(C)] forces Rust to form structures in memory just like in Sishechka. Without this, Rust has the right to optimize the order of fields and indents in the memory between them. When we work with raw pointers, in most cases we mean quite a specific structure in memory. Accordingly, #[repr(C)] allows us to state that Rust will allocate the structure in memory exactly as we assume.


Core



The os/kernel directory contains blanks for our OS kernel code. A call to make inside this directory will collect our nucleolus. The result of the build will be in the subdirectory build/ . In order to run this business you will need to copy build/kernel.bin to the root of the microSD card under the name kernel8.img . Currently, the kernel does nothing. By the end of this phase, the core will contain an interactive text shell with which to talk.



The kernel crate depends on the crate pi . You can see extern crate pi; in kernel/src/kmain.rs and an entry about this in Cargo.toml . Those. We can unambiguously use all types and constructions declared in pi .



Documentation



When writing drivers, the manual on the BCM2837 peripherals is very useful to us .



Subphase B: System Timer





In this subphase, we will write a driver for the built-in timer. The main work is carried out in the files os/pi/src/timer.rs and os/kernel/src/kmain.rs . The timer is documented on page 172 (section 12) of the BCM2837 peripheral manual .



First, look at the code that already exists in os/pi/src/timer.rs . At least these parts are:



 const TIMER_REG_BASE: usize = IO_BASE + 0x3000; #[repr(C)] struct Registers { CS: Volatile<u32>, CLO: ReadVolatile<u32>, CHI: ReadVolatile<u32>, COMPARE: [Volatile<u32>; 4] } pub struct Timer { registers: &'static mut Registers } impl Timer { pub fn new() -> Timer { Timer { registers: unsafe { &mut *(TIMER_REG_BASE as *mut Registers) }, } } } 


There is one line of code with unsafe that you should pay attention to first. In this line, the TIMER_REG_BASE address in *mut Registers cast, and then immediately turned into &'static mut Registers . In fact, we are reporting growing that we should have a static link to the structure at TIMER_REG_BASE .



What exactly is there at TIMER_REG_BASE ? On page 172 you can find the manual that 0x3000 is offset from the beginning of the periphery for the timer. Those. TIMER_REG_BASE is the address from which the registers of the timer itself begin. After one line with unsafe we can use the registers field for quite secure access to all this. For example, we can read the register CLO using self.registers.CLO.read() or write to

CS with self.registers.CS.write() .



Why can't we write to the CLO and CHI registers? [restricted-reads]

')

The BCM2837 documentation states that the CLO and CHI registers are read only. Our code provides this property. How? What prevents us from writing to CLO and CHI ?





What exactly is not safe?



In short, unsafe is a marker for the Rust compiler, saying that you take control of memory security. The compiler will not protect you from memory problems in these pieces of code. In unsafe portions of the code, Rust allows you to do everything that you can do in Nyashny Xi. Can rob caravans free enough to cast one type to another, play with raw signs, create lifetimes.



However, note that the code in the unsafe block can be very dangerous . You need to make sure that what you are doing in the insecure section is actually safe. It is more complicated than it seems at first glance. Especially for the reason that the security concepts in Rust are stricter than in other languages. We must try not to use unsafe at all. As far as possible of course. For things like operating systems, we need to use unsafe if we want to communicate directly with the hardware. But we will limit the use of it as much as possible.



If you want to read the moar about unsafe - you should look at chapter 1 of the Nomicon . There and further on this little book you can learn a lot from the useful for a variety of strong witchcraft in Rust.


Driver implementation



Implement Timer::read() from os/pi/src/timer.rs . Then the current_time() , spin_sleep_us() and spin_sleep_ms() methods can be found nearby. Comments and the names of these functions fully indicate their expected functionality. To implement Timer::read() will need to read the BCM2837 documentation in the appropriate section. At the very least, you should understand which registers will need to be read to get the entire 64-bit value of the timer. You can build pi crate with the cargo build . Although it will be faster to simply check the correctness of the written with the help of cargo check .



Driver testing



It will not be superfluous to make sure that the spin_sleep_ms() function is implemented correctly. To do this, write the appropriate code in kernel/src/kmain.rs .



Copy the LED flashing code from phase 4 zero labs. Instead of the sleep function, which is simply spinning in a loop, you should use our spin_sleep_ms() function to create pauses between blinks. Recompile the kernel and load it onto a memory card named kernel8.img . Start everything up and make sure that the LED is blinking at the frequency you have planned. Try to set a different delay size and make sure everything works. Yes, constantly poking back and forth microsd-card is quite tiring. By the end of this part we will have a bootloader that will solve this problem.



If your implementation of the driver for the timer works, then you can go to the next subphase.



Subphase C: GPIO



In this subphase, we will write a generic, independent of a specific pin number, GPIO driver. The main work is carried out in the files os/pi/src/gpio.rs and os/kernel/src/kmain.rs . GPIO documentation can be found on page 89 (section 6) of the BCM2837 peripherals manual .



State machines





All hardware devices can in fact be considered finite automata ( eng ). They are initialized with some state and go to other states explicitly or not. At the same time, the devices provide different functionality depending on the current state. In other words, in some specific states, only a certain set of transitions to other states is operable.



Most programming languages ​​make it impossible to precisely follow the semantics of finite automata. But this certainly does not apply to Rust. Rust allows us to follow this semantics quite clearly. This is what we will use to implement a more secure GPIO driver. Our driver will ensure that each GPIO pin will always be used correctly. At compile time.



* It looks like some kind of research ...



You caught me. In essence, this is my area of ​​study at this time. - Sergio

Below you can see the state diagram for a subset of the GPIO state machine property (for one pin):





Our goal is to implement it all in Rust. To begin with, this diagram tells us sobsna:





What transitions did you use in lab 0? [blinky-states]



When you wrote the code for Phase 4 from Labs 0, you essentially implicitly implemented a subset of our state machine. What state transitions did this take place?

We will use the Rust type system to provide assurances that the pin can only SET and CLEAR if it is in the OUTPUT state and only in LEVEL if in the INPUT state. Take a look at the GPIO structure declaration from the pi/src/gpio.rs :



 pub struct Gpio<State> { pin: u8, registers: &'static mut Registers, _state: PhantomData<State> } 


The structure has one generalized argument named State . It is used only by PhantomData and no one else. Actually for the sake of such PhantomData it exists: in order to convince Rust that the structure somehow uses a generalized argument. We are going to use State as a marker of the state of the Gpio . At the same time, we still need to ensure that a specific value for this parameter cannot be created.



Macro state! generates types that seem to be there, but you can't create them. In this case, it generates a list of states in which Gpio can be:



 states! { Uninitialized, Input, Output, Alt } //        -  : enum Input { } 


It looks weird. Why do we need to create enums without any possible values? They have one nice touch. They can not be created. But they can be used as markers. No one can ever pass us a value of type Input because it cannot be created. They live and exist only at the level of types and nowhere else.



Then you can implement methods for each state with the appropriate set of transitions:



 impl Gpio<Output> { ///   pub fn set(&mut self) { ... } ///   pub fn clear(&mut self) { ... } } impl Gpio<Input> { ///      pub fn level(&mut self) -> bool { ... } } 


This is similar to the guarantee that Gpio can be Gpio only in a strictly defined way, depending on the state. Not bad, huh? But how do we achieve these states? To do this, we have the Gpio::transition() method:



 impl<T> Gpio<T> { fn transition<S>(self) -> Gpio<S> { Gpio { pin: self.pin, registers: self.registers, _state: PhantomData } } } 


This method allows you to easily and freely transfer Gpio from one state to another. Receives Gpio in state T and gives Gpio in state S Note that it works for any S and T We must use this method very carefully. If we make a mistake in all this, then our driver can be considered written incorrectly.



In order to use transition() we need to specify the type S for Gpio<S> . We provide Rust with enough information so that he can get it all out on his own. For example, the implementation of the method into_output :



 pub fn into_output(self) -> Gpio<Output> { self.into_alt(Function::Output).transition() } 


This method requires that its return type be Gpio<Output> . When the Rust type system looks at the transition() call, it looks for a Gpio::transition() method that Gpio<Output> returns. It finds a method that returns Gpio<S> , which exists for any S Accordingly, instead of S you can safely substitute Output . As a result, it converts Gpio<Alt> (from the function into_alt ) to Gpio<Output> .



What will be wrong if the client can transfer arbitrary states? [fake-states]



Think about what happens if we let the user code freely choose the initial state for the Gpio structure. What can go wrong?





Why is this all possible only in Rust?



Notice the little fact that into_ transitions use the semantics of the move. This means that as soon as Gpio goes into another state, it can no longer be available in the previous state. Until the type implements Clone , Copy and some other duplication methods, the reverse transition is not available. No other language can do that. Even C++ . Such a witch at the time of compiling with all the guarantees is only here. (A guru in the pros or anything else may try to challenge this statement)


Driver implementation



Write all the necessary code instead of unimplemented!() In the file pi/src/gpio.rs From the comments and signatures of all these methods can be understood by deduction their expected functionality. It is worth it to consult the documentation (page 89, section 6 of the BCM2837 manual ). Do not forget about the utility of cargo check .



Hint: remember that you can create arbitrary lexical scopes with curly braces { ... } .


Driver testing



Obviously, to test the driver, we need to write some code in the kernel/src/kmain.rs .



This time, instead of reading / writing directly into the registers themselves, we will use our driver to flash the LED. By turning on / off the GPIO pin number 16. At the same time, the whole code will look much cleaner and more elegant. Compile the kernel, load it on the card with the name kernel8.img and run the malinka with it all. The LED should flash exactly the same as before.



Now you can connect more LEDs. Use the GPIO pins numbered 5, 6, 13, 19, and 26. Refer to the diagram with pin numbers from the zero labs to determine their physical location. Let the core flash as many LEDs as you wish!



Which blinking pattern have you chosen? [led-pattern]



What scheme did you decide to turn on / off the LEDs? You can choose many options to your taste. But if the choice is tight - you can turn them on and off in a circle. image

As soon as your GPIO driver becomes fully operational, you can proceed to the next subphase.



Subphase D: UART



In this subphase, we will write a mini UART device driver, which is embedded in the percent of our raspberry. Most of the work is done in the files os/pi/src/uart.rs and os/kernel/src/kmain.rs . The Mini UART is documented on pages 8 and 10 (sections 2.1 and 2.2) of the BCM2837 manual .



UART: Universal Asynchronous RX / TX



UART ( ru ) or Universal Synchronous ReceiverTransmitter is a device and a serial protocol for communicating hardware with just two wires. These are the same two wiring (rx / tx) that were used in phase 1 of the zero labs in order to connect the UART device on the CP2102 USB module to the UART device on a malink. On the UART, you can send any data: text, binary files, pictures with cats and what else there is enough imagination. As an example, right in the next sub-phase, we will write an interactive shell that will read from the UART on the Malinka and write to the UART on the CP2102. In phase 4, we will transfer binary information in about the same way.



The UART protocol has several configuration parameters. Both the receiver and transmitter must be configured identically in order for it to work. These are the parameters:





Mini UART does not support parity bits and only supports one stop bit. Thus, we only need to configure the baud rate and frame length. A little more about the UART itself can be found in a document called Basics of UART Communication (needs translation?).



Driver implementation



At this stage, we have all the necessary tools for writing a device driver without having to paint each step. My congratulations!



The task is to implement everything you need in the file pi/src/uart.rs You need to add the contents of the Registers structure. In this case, use a variant of the Volatile type with the minimum necessary set of possibilities for each register. Registers that are read-only should use ReadVolatile . If only WriteVolatile allowed, then WriteVolatile . For reserved space there is Reserved . new() 115200 ( 270) 8 . unimplemented!() , . fmt::Write , io::Read io::Write MiniUart .



: LCR , BAUD CNTL new /



: GPIO .




, ( kernel/src/kmain.rs ), . :



 loop { write_byte(read_byte()) } 


screen /dev/<_> 115200 UART. screen TTY . , . Those. . :



 loop { write_byte(read_byte()) write_str("<-") } 


, β€” .



E: The Shell



UART . os/kernel/src/console.rs , os/kernel/src/shell.rs os/kernel/src/kmain.rs .



Console





, , - / . Unix stdin stdout . Console . Console kprint! kprintln! . , print! println! . . Console , .



os/kernel/src/console.rs . Console . - MiniUart . . . MiniUart MiniUart Console .





β€” , . Rust. Rust . , ? , unsafe . : Rust'y, , .. , "" . , . Rust . :



 //      ! fn make_mut<T>(value: &T) -> &mut T { unsafe { /*      */ } } 


. . , , unsafe Rust. , . " ". Those. . .



, . , . , ( & ). , ( &T -> &mut ).



. , , :



 fn lock<T>(value: &T) -> Locked<&mut T> { unsafe { lock(value); cast value to Locked<&mut T> } } impl Drop for Locked<&mut T> { fn drop(&mut self) { unlock(self.value) } } 


Mutex . β€” , :



 fn get_mut<T>(value: &T) -> Mut<&mut T> { unsafe { if ref_count(value) != 0 { panic!() } ref_count(value) += 1; cast value to Mut<&mut T> } } impl Drop for Mut<&mut T> { fn drop(&mut self) { ref_count(value) -= 1; } } 


, RefCell::borrow_mut() . β€” , :



 fn get_mut<T>(value: &T) -> Option<Mut<&mut T>> { unsafe { if ref_count(value) != 0 { None } else { ref_count(value) += 1; Some(cast value to Mut<&mut T>) } } } impl Drop for Mut<&mut T> { fn drop(&mut self) { ref_count(value) -= 1; } } 


RefCell::try_borrow_mut() . " ": . Console Mutex . std::Mutex β€” . . kernel/src/mutex.rs . , , , Rust. Mutex , , .



So. CONSOLE kernel/src/console.rs . kprint! kprintln! , . , Console β€” Console . CONSOLE Console .



Rust Sync .



T static , T Sync . , Rust . , Rust , . Send Sync , Rust .





** &mut T ? [drop-container]



, , Drop . , &mut T ?





write_fmt ? [write-fmt]



_print write_fmt MutexGuard ( Mutex<Console>::lock() . write_fmt ?


Console



, unimplemented!() kernel/src/console.rs . kprint! kprintln! , kernel/src/kmain.rs , , . , print! println! . screen /dev/<-> 115200 .



...



println! β€” Rust. printf . Rust , , . . , ? .





: Console : .




Finished product



. kernel/src/shell.rs . Command . Command::parse() Command . parse args StackVec , buf . Command::path() .



( Command , StackVec , Console CONSOLE , kprint! , kprintln! , ) shell . prefix , . "> " . , . ad-infinitum . . echo .



, :





shell . kernel/src/kmain.rs . SOS, , . , . β€” . .



:



b'a' u8 'a'



\u{b} ASCII b



\r \n



, backspace, , backspace



StackVec



std::str::from_utf8





std !



, std . . , , xargo doc --open os/std .





? [shell-lookback]



. , .


4:



, , Raspberry Pi. os/bootloader/src/kmain.rs



, MicroSD- . , , . , .



β€” "", , XMODEM UART. , . ttywrite . :







Raspberyy Pi 3 kernel8.img 0x80000 . , , kernel8.img 0x80000 ARM' (program counter) 0x80000 . , . , 0x80000 .



(linker, ). . : , . , . os/kernel/ext/layout.ld ( ). , 0x80000 . 0x80000 .



, , 0x80000 . . 0x80000 . Those. ! . . . . How?





. os/bootloader/ext/layout.ld , , 0x4000000 . , 0x80000 . kernel_address config.txt . bootloader/ext/config.txt . , . Those. MicroSD-.



0x80000 0x4000000 "" .



63.5 ? [small-kernels]



, , , . β€” . , . ?



, . macOS - /System/Library/Kernels/kernel . /mach_kernel . Linux - /boot/ vmlinuz , vmlinux bzImage . ? 63.5 ?




bootloader/src/kmain.rs . , , . const . jump_to , addr . . pi xmodem UART, , . , .



, XMODEM, ( 750 ). . β€” . , β€” . os/kernel/build/kernel.bin ttywrite . β€” , screen .



? [bootloader-timeout]



. ?





config.txt , !



:



kmain() 15 .



std::slice::from_raw_parts_mut .



&mut [u8] io::Write .

UPD

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



All Articles