このパートでは、 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つだけを使用します。 彼らは私たちにとって興味深いです：
| 名 | タイプ（ tag
） | 大きさ | 説明 |
|---|---|---|---|
| コア | 0x54410001 | 5または2（空のリストの場合） | スターターとして使用 |
| なし | 0x00000000 | 2 | 終わりを意味する |
| 思い出 | 0x54410002 | 4 | 物理メモリの一部を説明します |
| CMDLINE | 0x54410009 | 違う | カーネルに引数を渡す |
タグのタイプによって、ヘッダーの後のデータの解釈方法が決まります。 名前に関連付けられているリンクをクリックすると、詳細を確認できます。 たとえば、 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]
! , ? ( ) .
