最初からオペレーティングシステム。 レベル2（後半）

このパートでは、 Vec 、 String 、 HashMapなどの使用をロック解除するために、メモリマネージャーを作成します。 その直後に、FAT32ファイルシステムを実装し、EMMCのドライバー（SDカードと通信するためのもの）を接続します。 最後に、シェルにcd 、 pwd 、 cat 、 lsの新しいコマンドがいくつか表示されます。

ゼロラボ

最初のラボ： 若い半分と古い半分

有用性

• 本はRustバージョン2にあります。 ロシア語では、翻訳は最後まで完了していません。 だからマークダウンのみ。
• 標準ライブラリRustの参照 。
• BCM2837プロセッサの周辺のマニュアル 。
• ATAGSヘルプ
• FAT構造の簡単な説明
• 英語版ウィキペディアのFAT32に関する記事 。

フェーズ0：はじめに

まず、最初から環境に何も変わっていないことを確認します。

• そこにLinux、BSDまたはmacOS
• 64ビットです
• USBポートがあります

さらに、これがインストールされます： git 、 wget 、 tar 、 screen 、 makeおよび最後のシリーズにあったすべてのもの。 私たちは安定性を確信し、前進します。

必要なコードを取得する

このリポジトリを、 cs140eという名前のパパ（または、そこにあるもの）にcs140eします。

 git clone https://web.stanford.edu/class/cs140e/assignments/2-fs/skeleton.git 2-fs 

結局のところ、内部には次のようなものがあるはずです。

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

ここで、コードの一部があるosリポジトリを、この部分で使用されるコードとマージする必要があります。

 cd os git fetch git checkout 2-fs git merge master 

マージの競合を解決する必要がある場合があります。 次のようなものが表示される場合があります。

 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. 

自動的に失敗しました。 手にする必要があります。 これを解決するには、 kmain.rsを手動で変更する必要があります。 以前のシリーズからのすべての変更を必ず保存してください。 競合を解決するには、 git addおよびgit commitを使用して固定ファイルを追加する必要があります。 マージの競合の解決に関する一般的な情報、および一般的なgitに関する情報は、 githowto.comマニュアルにあります 。 このチュートリアルを実行できます。 何でも重宝します。

ファームウェアの更新

2-fs turnipからmake fetchを使用してファームウェアを再ダウンロードする必要があります。 チーム自体がすべてをダウンロードして解凍します。 files/サブディレクトリからMicroSDカードのルートにファイルを配置するだけです。 つまり、ファイルfirmware/bootcode.bin 、 firmware/config.txt 、 firmware/fixup.datおよびfirmware/start.elf 。 kernel8.imgとして前の部分のブートローダーを使用する場合、この行をconfig.txtに追加する必要があることを忘れないでください：

 kernel_address=0x4000000 

ttywriteをインストールする

これで、 os/kernelのMakefile追加のinstallターゲットが追加されました。 カーネルを収集し、前の部分のttywriteを使用してttywriteに直接送信します。 したがって、 kernel8.imgにkernel8.img以前のシリーズで書かれたブートローダーが含まれている場合、このまさにブートローダーはファイルを受け入れてカーネルにロードします。 これを実行make installは、パパでカーネルコードを使用してmake installを実行make install必要があります。

同時に、 Makefileからのこのターゲットは、名前だけでttywrite直接呼び出します。 つまり ttywriteは、 PATH環境変数が指す場所のいずれかになければなりません。 これらの場所の1つにttywriteために、1 1-shell/ttywrite 、 cargo installを実行できます。 当社のユーティリティが収集し、適切な場所にコピーします。 すべてが正しい場合、 ttywrite --helpを呼び出すとヘルプが表示されます。

デフォルトでは、 make installはデバイス名に/dev/tty.SLAB_USBtoUARTを使用します。 Makefileを編集して、必要なものを示します。 つまり アダプタにはどのデバイスがありますか？ PI_TTYという変数があります。 異なる意味を与えてください。

ALLOCATOR.initialize()はパニックを引き起こします！
シェルは引き続き機能するはずです。 ただし、 make installターゲットをテストしようとすると、シェルが機能していないことがわかります。 ほとんどの場合、問題はALLOCATOR.initialize()呼び出しにあります。 メモリアロケーターはありません。 警告なしで実行されると、単にパニックになるスタブのみ。 少し後でこの迷惑な事実を修正します。 とりあえず、この行をコメントアウトするだけで、多かれ少なかれそれでも機能します。

フェーズ1：メモリライン

このフェーズでは、2つのメモリアロケーターを実装します。 最も単純なバンプアロケーターとやや複雑なビンアロケーター。 ヒープ上のメモリ割り当てが機能するために必要なのは、実際にはこれだけです。 つまり、 Vec 、 Box 、およびString引き続き機能します。 使用可能なメモリの量を判断するために、ARMタグ（ ATAGS ）を使用します。 さらに、 panic!呼び出されたときに最終的に呼び出されるpanic_fmt関数の内部を実装する必要がありpanic! 。

サブフェーズA：パニック！

panic_fmtの実装から始めましょう。 kernel/src/lang_items.rs 。

言語アイテム

Rustコンパイラが、オペレーティングシステム（Raspberry Piなど）を使用しない目的でプログラムをコンパイルするように構成されている場合、コンパイラはいくつかの機能を要求します。 私たちは自分の手でそれらを書く必要があります。 そのようなものは言語項目と呼ばれます。 これらの要素は、特定の条件下でコンパイラが呼び出しを置き換える関数です。 このような関数は、あらゆる基本言語に対して定義できます。 これを行うには、そのような関数に#[lang_item]属性で注釈を付ける必要があります。

Rustでは現在、これらの関数のうち2つだけが必要です。

• panic_fmt: (fmt: ::std::fmt::Arguments, file: &str, line: u32, col: u32) -> ! panic!呼び出されたときに呼び出されpanic! 。 引数panic! パラメータfmtとして渡されます。 さらに、 panic!が呼び出された場所のファイル名、行および列番号panic! 。 これは、それぞれfile 、 line 、およびcolです。
• eh_personality ：この関数は、特定のOSまたはABIに依存します。 必要に応じて、 スタックのアンワインド時またはアボート後に呼び出されます 。 通常、これはすべてpanic!発生しpanic! またはストリームを終了します。 この関数は実装しません。

これらの関数は両方ともkernel/src/lang_items.rsですでに宣言されていkernel/src/lang_items.rs 。 関数panic_fmtを追加して、有用なものを表示する必要があります。

panic_fmt実装

次に、この関数を追加します。 実装では、送信された情報をコンソールに出力してから、無限ループloop 。 ところで。 fmt::ArgumentsはDisplayトレイトを実装します。 したがって、 kprintln!("{}", fmt) ）を使用できます。 個人的に好きなように結論を出します。 たとえば、Linuxカーネルのパニックからインスピレーションを受けることができます 。

  ( ( ) ) ) ( ( ( ` .-""^"""^""^"""^""-. (//\\//\\//\\//\\//\\//) ~\^^^^^^^^^^^^^^^^^^/~ `================` The pi is overdone. ---------- PANIC ---------- FILE: src/kmain.rs LINE: 40 COL: 5 index out of bounds: the len is 3 but the index is 4 

次に、ある種のカーネルパニックでpanic_fmt実装panic_fmtテストします。 make installを使用してコンパイルし、ブートローダーを介して実行できることを思い出してください。 はい。 ALLOCATOR.initialize()がpanic! どこか中。 したがって、実行すると、エラーメッセージも表示されるはずです。

これに加えて、多くの方法でパニックを引き起こすようにしてください。 Using panic!() 、他の同様のマクロを使用します。 そして何か他のもの。 実装が自分で機能していることが確実な場合は、次のフェーズに進みます。

サブフェーズB：ATAGS

このサブフェーズでは、raspberryファームウェアが提供するARMタグ（ATAGS）に対してイテレーターを実行します。 反復子を使用して、使用可能なメモリの量を決定します。 主な作業は、 pi/src/atagsとkernel/src/allocator/mod.rs 。

ARMタグ

ATAGSまたはARMタグは、さまざまな情報をオペレーティングシステムのカーネルに転送するために、ARMブートローダーとファームウェアで使用されるメカニズムです。 Linuxは、ATAGSを使用するように構成することもできます。

Malinkaは、アドレス0x100から始まるATAG構造体の配列を配置します。 この場合、各タグは8ビットのヘッダーで始まります。

 struct AtagHeader { dwords: u32, tag: u32, } 

dwordsフィールドには、タイトル自体を含むタグ全体のサイズが含まれます。 ダブルワード（ダブルワード、つまり32ビットワード）のサイズ。 最小サイズは2 （ヘッダーのサイズ）です。 tagフィールドには、タイプATAGが含まれます。 ATAGSヘルプにはこれらの約12があります。 Malinkaはそのうちの4つだけを使用します。 彼らは私たちにとって興味深いです：

タグのタイプによって、ヘッダーの後のデータの解釈方法が決まります。 名前に関連付けられているリンクをクリックすると、詳細を確認できます。 たとえば、 MEMタグには次のようなものが含まれます。

 struct Mem { size: u32, start: u32 } 

タグは、それらの間を埋めることなく連続してメモリ内にあります。 このリストは、 COREタグで始まります。 そして、このリストの最後のタグはNONEです。 他のすべては任意の順序にすることができます。 次のタグがどこから始まるのかをdwordsは、 dwordsの内容を調べる必要があります。 グラフィカルには、すべて次のようになります。

組合と安全

ATAGタグの生の構造は、 pi/src/atags/raw.rsファイルで宣言されています。 同時に、そこでunion使用されます。 Rustの結合は、Neat Cの結合とほとんど同じです。 一部のフィールドがメモリを共有する構造を定義します。

 pub struct Atag { dwords: u32, tag: u32, kind: Kind } pub union Kind { core: Core, mem: Mem, cmd: Cmd } 

つまり、関連付けにより、正しい選択を考慮せずに、任意の構造をメモリに書き込むことができます。 Rustでは、特定のユニオンフィールドへのアクセスは安全ではないことがわかりました。

多くの場所に既にunsafeラッパーがあります。 少なくとも、自分で協会に連絡する方法について心配する必要はありません。 ただし、ライブラリのエンドユーザーに関連付けを渡すことはお勧めできません。 このため、ファイルpi/src/atags/atag.rsには別のAtag構造があります。 この構造は、アクセスに対して完全に安全です。 外部コードに渡すのは私たちです。 atagモジュールを追加すると、内部表現とこの構造の間の変換を記述します。

関連付けをエンドユーザーに渡すのはなぜ悪い考えですか？ [エンドユーザー安全]

安全でない構造物の安全なインターフェイスを作成するために多くの努力をしました。 これは、Rustで複数回表示されます。 標準ライブラリもこの好例です。 安全なレイヤーを作成する用途は何ですか？ このアプローチをNeat Cなどの言語に翻訳できますか？

コマンドライン引数

CMDLINEタグには特に注意が必要です。 このタグは次のように宣言されます。

 struct Cmd { /// The first byte of the command line string. cmd: u8 } 

コメントによると、 cmdフィールドには文字列の最初のバイトが含まれています。 言い換えると、 &cmdはCに似た文字列へのポインターであり、最終的にはゼロバイトで終了します。 このタグの安全なバージョンはCmd(&'static str)です。 rawバージョンから安全なバージョンに変換する場合、この行のサイズを決定する必要があります。 つまり nullターミネータ（コード0文字）を見つけます。 その後、アドレスとサイズを使用して、これをslice::from_raw_parts()を使用してスライスに変換できます。 次に、このスライスは、 str::from_utf8()またはstr::from_utf8_unchecked()を使用して文字列に変換できます。 既にラボ1で使用しています。

atags実装

まあ。 これで、 pi/src/atagsあるatagsモジュールを実装するために必要なものがすべてpi/src/atags 。 atags/raw.rsからraw::Atag::next()をatags/raw.rsからatags/raw.rs このメソッドは、現在のATAGの次のATAGのアドレスを決定します。 ここでは、 unsafeコードに頼らなければなりunsafe 。 次に、 raw構造から安全な構造に変換するためのヘルパーメソッドとプロパティを実装します。これはatags/atag.rs From<&'a raw::Cmd> for Atagする場合、少しunsafeでunsafeコードを使用するFrom<&'a raw::Cmd> for AtagがFrom<&'a raw::Cmd> for Atagます。 Atags 、 atags/mod.rsにあるatags/mod.rsのIterator traitを実装しatags/mod.rs ここでは、少しunsafeコードも必要になる場合があります。

ヒント：

3行のコードでAtags::next()メソッドを実装できます（少なくとも試してみてください！）。

x: &Tから*const u32変換できますx as *const T as *const u32です。

x: *const Tから&Tへの逆変換は、 &*x実行できます。

add（） sub（）またはoffsetを使用して、生のポインターで算術演算を実行できます。

atagsテスト

ATAGSの独自の実装をテストします。 イテレータを介してすべての値を取得し、すべてをコンソールに出力してみてください。 kernel/src/kmain.rs直接移動しkernel/src/kmain.rs 。 NONE以外の3つのタグのうち少なくとも1つが表示されるはずです。 同時に、各ATAGの実装が期待どおりであることを確認してください。 実装が完了したら、次のサブフェーズに進みます。

ヒント ：構造のより美しい出力をコンソールに出力するには、 `{：＃？}を使用します。

タイプCMDLINEタグには何がCMDLINEますか？ [atag-cmdline]

これらのタグに値はありますか？ ファームウェアからどのような議論がありましたか？ どこから来たと思いますか、どのように使用できますか？

MEMタグに従って使用可能なメモリ量はどれくらいですか？ [atag-mem]

MEMタグで報告される使用可能なメモリの正確な開始アドレスとサイズは何ですか？ これはすべて、ラズベリーが持っている1ギガバイトのメモリにどれくらい近いですか？

サブフェーズC：ウォームアップ

このサブフェーズでは、2つのメモリアロケータの後続の書き込みに必要なすべてを準備します。 アドレスを2のべき乗に揃える関数align_upおよびalign_downを実装します。 さらに、システムメモリから開始アドレスと終了アドレスを返すmemory_map関数を実装します。 この関数は両方のアロケーターによって使用され、割り当てに使用可能なメモリー量を決定します。

アライメント

メモリ内のアドレスは、Nで完全に分割されると、Nバイトでアラインされたと呼ばれます N つまり、アドレスk k % n == 0が真になります。 通常、記憶を調整することを心配する必要はありません。 ただし、現在はシステムプログラマです。 このトピックへの注目が高まっているのは、ハードウェア、プロトコル、およびその他すべてが、アライメントに関して非常に特定のプロパティを規定しているという事実に関連しています。 たとえば、32ビットARMアーキテクチャでは、スタックポインターが8バイトにアライメントされている必要があります。 AArch64アーキテクチャ（この場合）では、スタックポインターに16バイトのアライメントが必要です。 x86-64でもほぼ同じことが必要です。 メモリのページのアドレスは、4キロバイトに揃える必要があります。 さらに多くの異なる例がありますが、それなしではできないことはすでにわかっています。

Cute Cでは、libCからアロケータによって返されるメモリアドレスは、32ビットシステムでは8バイト、64ビットシステムでは16バイトであることが保証されます。 さらに、呼び出し元は、返されたメモリアドレスのアライメントを明確に制御することはできず、自分で処理する必要があります。 このために、たとえば、POSIX標準のposix_memalign関数があります。

Neat Cでこのようなアライメントプロパティが選択されるのはなぜですか？ [libc-align]

mallocシステム関数のアライメントに8バイトまたは16バイトの保証を選択しても、根拠はありません。 標準Cライブラリでこのような保証が選択されたのはなぜですか？

Cute Cでは、 malloc()およびfree()宣言は次のようになります。

 void *malloc(size_t size); void free(void *pointer); 

Rustは、低安全レベルでallocとdeallocを使用します。これは次のようになります。

 // `layout.size()` is the requested size, `layout.align()` the requested alignment unsafe fn alloc(&mut self, layout: Layout) -> Result<*mut u8, AllocErr>; // `layout` should be the same as was used for the call that returned `ptr` unsafe fn dealloc(&mut self, ptr: *mut u8, layout: Layout); 

呼び出しコードは整列を示す場合があることに注意してください。 その結果、呼び出し元のコードではなくアロケーターが、整列されたポインターを返すように注意する必要があります。 次のサブフェーズでメモリアロケータを実装する場合、戻りアドレスが正しく整列されていることを確認する必要があります。

さらに、 deallocとは異なりdeallocでは、呼び出し側がallocとまったく同じLayout渡す必要があることに注意してdealloc 。 したがって、外部コードは、特定の割り当てられたメモリのサイズとアラインメントの格納に注意する必要があります。

このようにRustが責任をアロケーターと呼び出しコードとに分けていると思うのはなぜですか？ [onus]

キュートなアロケータでは、返すことができるメモリアドレスのアライメントに関する制限が少なくなります。 ただし、同時に、割り当てられたスペースのサイズを保持する必要があります。 Rustでは、まったく逆です。 なぜRustは反対の道を選んだと思いますか？ これはアロケーターと呼び出しコードにどのような利点がありますか？

align_up ： align_upおよびalign_down

次のサブフェーズでアロケーターを実装する場合、次または前のアライメントされたアドレスを判別するのに役立ちます。 つまり アドレスu次の>=または<= u 、2の累乗で整列されます。 align_upおよびalign_downが既に（もちろん実現されていalign_up ）ありalign_down 。 これらはkernel/src/allocator/util.rs 。 これらはおおよそ次のように宣言されます：

 /// Align `addr` downwards to the nearest multiple of `align`. /// Panics if `align` is not a power of 2. fn align_down(addr: usize, align: usize) -> usize; /// Align `addr` upwards to the nearest multiple of `align`. /// Panics if `align` is not a power of 2. fn align_up(addr: usize, align: usize) -> usize; 

これらの機能を今すぐリリースしてください。 kernelディレクトリからmake testまたはcargo test呼び出すmake testにより、このプロセスの正当性を確認できkernel 。 テスト自体はkernel/src/allocator/tests.rs 。 この部分のすべてが正しい場合、 align_utilすべてのテストにalign_utilはずです。

注意 ： kprint{ln}!テスト中kprint{ln}! print{ln}!呼び出しになりますprint{ln}! すべてが機能するはずです。

ヒント：

実装は1行または2行を占有します。

align_upとalign_downは互いに非常に似ています。

スレッドセーフ

libCのmalloc()および実装する2つのメモリアロケータはグローバルです。 つまり いつでもどこでも呼び出すことができます。 任意のストリームに含める。 したがって、アロケーターはスレッドセーフでなければなりません。 Rustはスレッドの安全性を非常に重視しています。 このため、システムに並行性を処理するメカニズム（スレッドなど）がまだない場合でも、アロケーターを実装することは困難です。

スレッドセーフメモリアロケーターのトピックは非常に広範囲です。 このトピックについては、多くの研究が見つかります。 現時点では、このトピックについては触れません。 MutexメモリMutexをラップするだけです。 このラッパーは既にkernel/src/allocator/mod.rs 今すぐこのコードをすべて読んでください。 Alloc特性の実装がそこにあることに注意してください。 これにより、Rustはこれが非常に有効なアロケーターであることを知ることができます。 , #[global_allocator] ( kmain.rs ). #[global_allocator] — , , Rust- Vec , String Box . つまり alloc() dealloc() , .

Alloc Allocator kernel/src/allocator/mod.rs imp::Allocator , mutex . imp . . #[path = "bump.rs"] , Rust-, . #[path] . bump- bump.rs . bin- bin.rs .

: memory_map

kernel/src/allocator/mod.rs — memory_map . Allocator::initialize() , kmain() . initialize() imp::Allocator .

memory_map . , . つまり , ATAGS. , . binary_end . , _end ( layout.ld ).

memory_map , Atags B binary_end . , . - String::from("Hi!") . . , panic!() bump-. memory_map , bump- — . , .

D: Bump-

. Bump-. kernel/src/allocator/bump.rs .

Bump- . alloc current . . current ( ). , . dealloc .

, , , 1 , 512 . , .

, kernel/src/allocator/bump.rs . つまり new() , alloc() dealloc() bump::Allocator . align_up align_down , . -. make test cargo test kernel . allocator::bump_* .

. , , !

saturating_add saturating_sub .

- , kmain() . :

 let mut v = vec![]; for i in 0..1000 { v.push(i); kprintln!("{:?}", v); } 

— .

alloc ? [bump-chain]

bump::Allocator::alloc() . ? : , v.push(i) bump::Allocator::alloc() .

E: Bin-

: bin-. kernel/src/allocator/bin.rs .

Bin- , . ( ) , . . — . , . .

, , . k - 2 2^n n , 3 k ( 2^3 , 2^4 … 2^k ). , 2^3 , 2^3 . 2^3 2^4 2^4 :

• bin 0 ( 2^3 ) (0, 2^3]
• bin 1 ( 2^4 ) (2^3, 2^4]
• bin 2 ( 2^5 ) (2^4, 2^5]
• bin k ( 2^k ) (2^(k - 1), 2^k]
• ...

(intrusive) . kernel/src/allocator/linked_list.rs . kernel/src/allocator/bin.rs LinkedList , .

?

next ( previous ) . . .

LinkedList::new() . push() . ( ), pop() . peek() . :

 let mut list = LinkedList::new(); unsafe { list.push(address_1); list.push(address_2); } assert_eq!(list.peek(), Some(address_2)); assert_eq!(list.pop(), Some(address_2)); assert_eq!(list.pop(), Some(address_1)); assert_eq!(list.pop(), None); 

LinkedList . iter() . . iter_mut() . Node , . value() pop() .

 let mut list = LinkedList::new(); unsafe { list.push(address_1); list.push(address_2); list.push(address_3); } for node in list.iter_mut() { if node.value() == address_2 { node.pop(); } } assert_eq!(list.pop(), Some(address_3)); assert_eq!(list.pop(), Some(address_1)); assert_eq!(list.pop(), None); 

LinkedList . , push() . LinkedList .

? [ll-alloc]

— . , , ?

, , . , . . , . . . .

:

• . , ( ). bin- .
• . , - . bin- , . .

, .

実装

bin- kernel/src/allocator/bin.rs . ( , bin- ) . . . - . make test cargo test . bump.rs bin.rs #[path] kernel/src/allocator/mod.rs . まあつまり bump-, bin, .

bin- — .

? [bin-about]

. :

• () ?
• ?
• ?

? [bin-frag]

! , ? ( ) .

UPD :