Operating systems from scratch; Level 1 (younger half)

This part is dedicated to improving Rust skills and writing a couple of useful utilities and libraries. Let's write drivers for GPIO, UART and the built-in timer. Implement the XMODEM protocol. Using this all, we will write a simple shell and loader. Before reading it is strongly recommended to make sure that you read the Book . At least from start to finish. For the lazy, but slightly more experienced, we can recommend this . In Russian, you can pick it up here .

Well, of course bypassing the zero level is absolutely not worth it. Also, about half of this part does not require raspberries.

Useful materials

• Book v2.0 by Rust. Translation into Russian on the way . Pull the translation team (and help them). This booklet is definitely worth reading at least to those who have not read.
• Documentation for the standard library Rust. There everything is ready, which is in the standard package.
• docs.rs - there you can read documentation on various libraries.
• Mana online download for free without registration and SMS. RTFM!
• Wiki article on the XMODEM protocol. For general development and those interested in the history of occurrence. For the implementation will help a little, almost no way.
• Another XMODEM document .
• BCM2837 - this is about the pro Malinki. In the same place as last time.

Phase 0: Getting Started

Just in case, be sure to use course-compatible hardware and software:

• Modern 64-bit Unix-like OS: Linux, macOS or BSD
• Do you have a suitable USB connector (unauthorized can use attachments)

In addition, the following programs should be installed: git , wget , tar , screen , make and all that was required for the zero level . For this part you will need to install socat .

If last time you managed to run everything you need under Windows, then this time everything should work. But if suddenly there is no, then no support. Neither I, nor the author of the original has a Venda at hand or a desire to dig into it.

Getting the code

You can clone the code for this part like this:

 git clone https://web.stanford.edu/class/cs140e/assignments/1-shell/skeleton.git 1-shell 

Feel free to explore the contents of the repository yourself.

Questions

There will be questions in this and all following labs. You can answer them directly in the comments using spoilers . Here is an example:

How do we configure and use other GPIO contacts? [assignment0]

Last time, we used a 16 pin GPIO in the name of LED blinking. Using the registers GPFSEL1 , GPSET0 and GPCLR0 . And if we use pin 27, which registers will be useful to us? And what is the physical contact of this 27 GPIO pin?

The square brackets indicate the file name inside the questions/ directories. This is not particularly important for us, since it is necessary to reply in the comments Do not read other people's answers until you are sure that you answered them yourself. Otherwise, not interesting. But these tags can be used as headlines for spoilers. But I advise you to first write in these files. For comfort.

Phase 1: Ferris Wheel (pun is not translated)

(This part can be completely skipped if you already have enough deep knowledge of Rasta.)

For the sake of training, we will edit the program on Rust with some selfish goals. Some should be compiled after editing. Others should not compile. For the third, tests should complete successfully.

In the bowels of the catalog ferris-wheel/ you can find the following:

• compile-fail - contains code that must be broken so that it does not compile
• compile-pass - contains code that needs to be fixed exactly before compilability
• run-pass - contains a code with tests that should be green
• questions - in theory for questions, but we have already agreed that you can put all this in the comments

There still is a test.sh test.sh . It checks the correctness of the assignments. If you run it, it will quite popularly explain where and what is not quite as expected. Sort of:

 $ ./test.sh ERROR: compile-pass/borrow-1.rs failed to compile! ERROR: compile-pass/const.rs failed to compile! ... 0 passes, 25 failures 

In addition, the script accepts the -v flag. If this same flag is passed to the script, then errors that the compiler spits out will be shown:

 $ ./test.sh -v ERROR: compile-pass/borrow-1.rs failed to compile! ---------------------- stderr -------------------------- warning: unused variable: `z` --> /.../ferris-wheel/compile-pass/borrow-1.rs:9:9 | 9 | let z = *y; | ^ | = note: #[warn(unused_variables)] on by default = note: to avoid this warning, consider using `_z` instead error[E0507]: cannot move out of borrowed content --> /.../ferris-wheel/compile-pass/borrow-1.rs:9:13 | 9 | let z = *y; | ^^ | | | cannot move out of borrowed content | help: consider using a reference instead: `&*y` error: aborting due to previous error ... 0 passes, 25 failures 

This script also accepts a string as a filter. If present, only those file paths ($ directory / $ filename) that match this filter will be checked. For example:

 ./test.sh trait ERROR: compile-pass/trait-namespace.rs failed to compile! ERROR: run-pass/trait-impl.rs failed to compile! 0 passes, 2 failures 

Does not interfere with one another and you can combine the filter and the -v key. Something like this: ./test.sh -v filter .

How much can I change?

Each file contains a comment, which indicates how much you can spoil it (diff budget). Those. The maximum number of changes that can be made to fix the program. Solutions that do not fit into this framework can be considered not passed.

For example. In the compile-pass/try.rs there is such a comment:

 // FIXME: Make me compile. Diff budget: 12 line additions and 2 characters. 

It says that you can add no more than 12 lines of code (blank lines are also considered). And change (add / change / delete) 2 characters. You can use git diff to see the line changes. And git diff --word-diff-regex=. for the same, but by character.

Another example:

 // FIXME: Make me compile! Diff budget: 1 line. 

It kakbe tells us that you can change (add / change / delete) only one line of code.

General rules

After the changes, the intended functionality of the programs should be preserved. Suppose that if the body of a certain function needs to be modified in such a way that it compiles, it will not be enough to add unimplemented!() . If you are in doubt - try the best of what you can. Well, or ask in the comments.

In addition, it is absolutely not recommended to do the following dirty methods:

• Change all these assert! s
• Modify everything marked as "do not modify"
• Change comments about how much and what can be changed
• Move, rename or add any files

When all tasks are completed test.sh will display 25 passes, 0 failures

Hint: the file name may contain the key to the solution.

Hint: in this cozy chats will answer faster questions about Rust. Faster than in the comments on this article.
')
What happened? What was repaired? Why does this work? [filename]

For each program from this part, you should explain what was wrong with the source code. Then clarify on hardcore what changes have been made and why these corrections do their dirty work. Good explanations are welcome. If you think that everything is so obvious to you, then you can not write. If laziness - you can not write anything at all.

Phase 2: Oxidation

At this stage, we will write a couple of libraries and one command line utility. We will work in the subdirectories stack-vec , volatile , ttywrite and xmodem . Here, too, there will be a number of questions that can be answered, if not broke. Each part is controlled by Cargo. At least here these commands can be called useful:

• cargo build - build a program or library
• cargo test - run tests
• cargo run - application launch
• cargo run -- $ - this way you can transfer flags when launching an application

About Cargo there is a separate booklet: Cargo Book . From there you can learn the necessary info about how it all works in detail.

Subphase A: StackVec

One of the most important features that operating systems deal with is memory management. When C, Rust, Java, Python, or practically any application in general calls malloc() , then when there is a shortage of memory, a system call is eventually used that requests additional memory from the operating system. The operating system determines whether there is still any memory unused. If so, then the OS will dry out a bit of the processor from this memory.

Memory allocation - non penis canis est

Modern OSes like all sorts of linups contain a lot of tweaks related to memory management. For example, in the order of optimization crutches, when a certain amount of memory is requested, it is allocated virtually. In this case, the physical memory is not allocated until the application tries to use this same memory. On the other hand, the application creates an illusion of simplified distribution. Operating systems are able to skillfully lie ( ).

Structures like Vec , String and Box inside use malloc() to allocate memory for their own needs. This means that these structures require support from the operating system. In particular, they require that OS was able to allocate memory. We have not even begun this part yet (see in the next series), so we don’t have any form of memory management. Accordingly, all these Vec we can not (yet) use.

This is a concentrated crap for Vec - a good abstraction suitable in all respects! It allows us to think in terms of .push() and .pop() without having to remember any subtleties. Can we get something like Vec without a full memory allocator?

Of course. The first thing that comes to mind is the preliminary allocation of memory with the subsequent transfer of it into some kind of structure that implements the necessary abstractions on top of this. We can allocate memory statically directly in a binary file, or somewhere on the stack. In both cases, such a memory must have a fixed size known in advance.

In this subphase, we will implement a StackVec structure that provides api, similar to the one provided by Vec from the standard library. But it uses a previously allocated piece of memory. This very StackVec will come in handy when implementing the command line (in phase 3). We will work in the stack-vec subdirectory. In it you can already find the following items:

• Cargo.toml - configuration file for Cargo
• src/lib.rs - here we will add the necessary code
• src/tests.rs - tests that will be run when you run the cargo test
• questions/ - blanks for files with questions (we are not very interested)

StackVec interface

StackVec<T> is created by calling StackVec::new() . The argument for the function new is a slice of type T The StackVec<T> implements many methods that are used in much the same way as those of Vec . For example, take StackVec<u8> :

 let mut storage = [0u8; 1024]; let mut vec = StackVec::new(&mut storage); for i in 0..10 { vec.push(i * i).expect("can push 1024 times"); } for (i, v) in vec.iter().enumerate() { assert_eq!(*v, (i * i) as u8); } let last_element = vec.pop().expect("has elements"); assert_eq!(last_element, 9 * 9); 

The StackVec type StackVec already declared in this form:

 pub struct StackVec<'a, T: 'a> { storage: &'a mut [T], len: usize, } 

Understanding StackVec

There are a couple of questions about the StackVec device:

Why does push return a Result ? [push fails]

The push method from Vec , which is from the standard library, does not have any return value. However, a push from StackVec has: it returns a result indicating that there may be some kind of error. Why StackVec::push() fail to complete, unlike Vec ?

Why do we need to limit T lifetime 'a ? [lifetime]

The compiler will reject the StackVec :

 struct StackVec<'a, T> { buffer: &'a mut [T], len: usize } 

If we add the restriction 'a to the type T , then everything will work:

 struct StackVec<'a, T: 'a> { buffer: &'a mut [T], len: usize } 

Why is this restriction required? What will happen if Rust does not follow this restriction?

Why StackVec require T: Clone for the pop method? [clone-for-pop]

The pop method from Vec<T> standard library is implemented for any T , however, the pop method for our StackVec is implemented only when T implements the Clone property. Why should this be so? What is wrong if this restriction is removed?

StackVec implementation

Implement all unimplemented!() Methods from StackVec in stack-vec/src/lib.rs Each method already has documentation (from it it is clear what is required of you for example). In addition to this, there are tests in the src/tests.rs file that help ensure the correctness of your implementation. You can run tests using the cargo test command. In addition, you need to implement the Deref, DerefMut and IntoIterator for the StackVec class. And trey IntoIterator for &StackVec . Without the implementation of these treit tests will not pass. As soon as you are sure that your implementation is correct and you are able to answer the proposed questions, go to the next subphase.

What tests require the implementation of Deref ? [deref-in-tests]

Read the entire test code from the str/tests.rs . What tests did not want to compile if there was no implementation of Deref ? And what about DerefMut ? Why?

In fact, the tests are not complete

The proposed unit tests cover the basic functionality, but they do not check every sneeze. Look for such spaces and add more tests to the god of tests in the name of great justice.

Hint: solving from the zero phase liftime task can be useful.

Subphase B: volatile

In this part we will talk about volatile memory accesses and read the code in the volatile/ subdirectory. We will not write our code, but there are questions for self-testing.

Like typical operating systems, compilers masterfully crank up very tricky tricks. In the name of optimization, they are doing something that only looks like what you have planned. In fact, there will be a very strong witch inside. A good example of such a witch is the removal of a dead code. When the compiler can prove that the code does not affect execution, the dead code is quickly and decisively cut out. Suppose there is such a code:

 fn f() { let mut x = 0; let y = &mut x; *y = 10; } 

The compiler may think a little and reasonably that *y never read after writing. For this reason, the compiler can simply exclude this part from the resulting binary file. Continuing to reason in this vein, the compiler finds it suitable to cut the declaration itself y and then x . In the end, the f() call will go under the knife.

Optimizations of this type are very useful and valuable. Thanks to them, programs are accelerated without affecting the results. True, in some cases, such frauds can have unintended consequences. For example, y will point to any register that is only writeable. In this case, writing to *y will have quite visible effects without having to read *y . If the compiler does not know this, then this part will simply get rid of this part at the optimization stage and our program will not work as expected.

How do we convince the compiler that reading / writing something like this affects our cozy little world by itself? That is what is meant by volatile memory accesses. The compiler is afraid not to optimize access to such sites.

Rusty volatile

In Rust, we can use the read_volatile and write_volatile to read and write raw pointers.

What kind of raw pointers are these?

Up to now, we have had time to become familiar with the links (which are &T and &mut T ). Raw (raw) pointers in Rust ( *const T and *mut T ) are the same links without tracking the borrow checker. Reading / writing using these very raw pointers can lead to the same foot injuries that can often be seen with C and C ++ fans. Rust considers such operations unsafe. Accordingly, it is all mandatory to mark unsafe label. More information about raw indexes is in the documentation .

Writing calls to read_volatile and write_volatile is sad enough each time (besides the fact that it can lead to annoying errors on the basis of depression). Fortunately for us, Rust gives us the opportunity to make our lives easier and safer. On the one hand, we can simply make a volatile wrapper (almost like the volatile keyword in a ny si) and ensure that every read / write will remain in our code. As a bonus, we can define a wrapper that is read-only or write-only (there is no such thing in the nursery, the trunk was given and you are spinning as you like).

Introduction to Volatile , ReadVolatile , WriteVolatile and UniqueVolatile

The volatile in the volatile/ directory (who would have thought?) Implements these four types, which do roughly what is evident from their name. Read more in the documentation. Call cargo doc --open directly in the volatile/ directory to actually read this very documentation in a convenient form.

Why is UniqueVolatile ? [unique-volatile]

Both Volatile and UniqueVolatile allow you to work with volatile memory accesses. Based on the documentation, what is the difference between these two types?

Open the code src/lib.rs Read the code in the mura of their own skills. After that (reading the code) answer the following couple of questions. How to finish - you can go to the next subphase.

How are read and write restrictions organized? [enforcing]

The types ReadVolatile and WriteVolatile make it impossible to read and write the pointer, respectively. How is this done?

What is the advantage of using traits instead of the usual methods? [traits]

On closer examination, you can replace that each of the types implements only one of its own new methods. All other methods somehow relate to the implementations of Readable , Writeable and ReadableWriteable . What is the profit from all this? Describe at least two advantages of this approach.

Why are read and write safe, and new unsafe? [safety]

What should be true about new so that read and write can be considered safe? Would it be safe instead to mark new as safe, and read and write opposite to unsafe?

Hint: read the documentation for all these methods.

Why do we force new use? [pub-constructor]

If the type Volatile was declared as follows:

 struct Volatile<T>(pub *mut T); 

then a value of type Volatile could be created using Volatile(ptr) instead of calling new . What is the use of creating our wrapper with the static call new ?

Hint: Consider the implications for security claims for both options.

What do macros do? [macros]

What readable! macros do readable! writeable! and readable_writeable! ?

Subphase C: xmodem

In this subphase we implement the XMODEM file transfer protocol ( xmodem/ subdirectory). The main work goes in the file xmodem/src/lib.rs

XMODEM is a simple file transfer protocol developed in 1977. It has checksums of the packets, cancellation of the transmission and the ability to automatically retransmit in case of errors. It is widely used to transmit information through serial interfaces like the UART. The main point of the protocol is simplicity. You can read more in the wiki: XMODEM (anyone can translate the article into Russian).

Protocol

The protocol itself is described in some detail in the text file Understanding The X-Modem File Transfer Protocol . We will repeat something from the description right here.

Do not base your implementation on an explanation from Wikipedia!

Although the explanation from pedevikii will be useful at a high level, many details will differ from what we will implement here. Use Pedewikia as a protocol review only.

XMODEM is quite a binary protocol: raw Baitics are received and sent. In addition, the protocol is half-duplex: at any time the sender or recipient sends data, but never both at once. And finally, this is a packet protocol: the data is divided into blocks (packets) of 128 bytes. The protocol determines which Baitics to send, when to send them, what they will denote and how to read them later.

To begin with, we define several constants:

 const SOH: u8 = 0x01; const EOT: u8 = 0x04; const ACK: u8 = 0x06; const NAK: u8 = 0x15; const CAN: u8 = 0x18; 

, NAK , NAK . , NAK , . NAK , .

, , . 1. (.. 255), 0.

, :

1. SOH
3. ( 255 - $_ )
5. 
   
   • 256
6. :
   
   • NAK , ( 10 )
   • ACK ,

, :

1. SOH EOT
   
   • ,
   • EOT —
2. 
   
   • —
3. 
   
   • ,
4. (128 )
5. 
   
   • Those. 256
6. 
   
   • , NAK
   • , ACK

, , , CAN . CAN — .

, :

1. EOT
2. NAK ( — )
3. EOT
4. ACK ( — )

, ( EOT ):

1. NAK
2. EOT ( , )
3. ACK

XMODEM

XMODEM . , . expect_byte , expect_byte_or_cancel , read_packet write_packet src/lib.rs . Xmodem : packet started . , .

expect_byte expect_byte_or_cancel . ( read_byte write_byte ) read_packet write_packet . , , transmit receive . / . , . cargo test . , — .

std.

std::io . std .

:
{read, write}_packet 33 .

io::Read io::Write (, , ).

? .

, .

D: ttywrite

ttywrite . XMODEM. xmodem . ttywrite/src/main.rs . test.sh . - socat .

?

, . . , . UART, .

TTY?
TTY — (TeltTYpe writer). , . ( ) . /dev/ , tty.

ttywrite - . structopt , clap . , , Cargo.toml . structopt . , , structopt .

, , --help . , cargo run -- . : cargo run -- --help . . main.rs . Opt . .

, ? [invalid]

. -f idk . structopt , ?

, . . , .

main serial::open . open serial , . open TTYPort , / / ( io::Read io::Write ). ( SerialDevice ).

ttywrite . , , opt main . , stdin . . . -r , . , xmodem . ( ).

XMODEM Xmodem::transfer Xmodem::transmit_with_progress . transmit_with_progress . :

 fn progress_fn(progress: Progress) { println!("Progress: {:?}", progress); } Xmodem::transmit_with_progress(data, to, progress_fn) 

test.sh ttywrite . :

 Opening PTYs... Running test 1/10. wrote 333 bytes to input ... Running test 10/10. wrote 232 bytes to input SUCCESS 

Tips

stdin io::stdin() .

io::copy() .

main() 35 .

TTYPort .

test.sh -r ? [bad-test]

-r . XMODEM. , ? XMODEM ? ?

UPD . . .