セキュリティ・キャンプ 2021 応募課題 公開
セキュリティ・キャンプ 2021 Y-I 自作OSゼミの選考を通過しました。SecHack365 '20 er がたくさん通っていて嬉しかったです。
課題を晒すのが流行っているようなので私も便乗して公開します。
低レイヤについては勉強し始めたばかりなので割とめちゃくちゃなことを言っているかもしれません。
動機
応募課題
「OS自作ゼミ」の応募課題は、3問の共通課題と、3問の選択課題から成ります。共通課題は当ゼミに応募する方は全員回答してください。選択課題は、後で示す通りに回答してください。回答は、ソースコードを除いて全体が2,000字に収まるようにしてください。英数字や記号、改行文字も1文字とカウントします。複数の選択課題に回答する場合も字数制限は変わらないので、注意してください。
共通課題A
OS自作ゼミで挑戦してみたいことを教えてください。また、それを実現するために必要となる実装や調査することを想像して書いてください。間違っていても大丈夫です。
NimによるMikanOSの再実装に挑戦したいと考えています。
私はゼロからのOS自作入門を読み、初めてOS自作に取り組みました。非常に面白く、今まで自分が何気なく使ってきたものが、画面に文字を表示するだけでこれほどに難しく、大変で、多くの処理が動いていることを知りました。OSばかりか低レイヤプログラミングに取り組むこと自体が初めてなのでなかなかきちんと理解しているか分からないところがあります。
単に写経するだけでなく他の言語で再実装することでより深く理解し、低レイヤにおけるNimの扱い方についても学ぶことができると考え、このテーマを設定しました。
MikanOSはUEFIはC言語で、カーネル本体はC++で実装されています。Nimはどちらに対してもFFIによってヘッダファイルを読み込んで資産を運用できるため、他言語より比較的簡単に移植可能だと思います。
また、https://github.com/dom96/nimkernel で実装されているようにos:standaloneオプションを用いて組み込み向けに出力することができます。これにより、OS開発が可能です。
5月17日から第7章まで全てのコードを写経しながら https://github.com/momeemt/own-mikanos で進めており、当日までには少なくとも一周は読了し、実装し終える予定です。実装はこの本を参考にし、Nim固有の規格やコンパイラの仕様については https://nim-lang.org/docs/nimc.html#nim-for-embedded-systems などを読んで調査します。
共通課題B
"http://osdev.jp/" とWebブラウザのアドレスバーに入力してから、その内容が画面に表示されるまでの間には、コンピューターの中でさまざまな処理が行われています。そのなかで、あなたが大事だと思うOSの処理について、いくつか取り上げて説明してください。
多くのOSではTCP/IPプロトコルをを採用しており、トランスポート層までをカーネル内で実装されます。これにより、異なるOS間であっても通信することができるので、どんなサーバで運用されているWebページでもアクセスすることができます。私が重要だと感じたネットワーク処理について、カーネルが処理する部分を説明します。
アドレスバーに入力されたURLのWebサーバのホスト名を元に、DNSサーバに問い合わせ、WebサーバのIPアドレスを解決します。また、ARPリクエストを送信してイーサネットのMACアドレスを解決します。これらを用いて、サーバに対してTCPコネクション確立を要求します。その後、サーバからの要求に応答してコネクションを確立させます。確立後はHTTPリクエストによってコンテンツがやり取りされますが、それはシステムプロセスが実行します。
参考文献: https://ja.wikipedia.org/wiki/オペレーティングシステム https://www.n-study.com/tcp-ip/conclusion-of-webaccess/
共通課題C
C言語で連想配列を実装してください。連想配列のキーは文字列、値は整数とします。最低限、連想配列に要素を挿入する関数map_put、要素を検索する関数map_find、要素を削除する関数map_removeを作ってください。C標準ライブラリのみを利用して実装してください。
キーが与えられると文字列からハッシュが計算され、Map型のメンバvalueに代入されます。最悪時間計算量もキーの文字数をmとするとO(m)であり高速です。
#include <stdio.h>
#include <string.h>
typedef struct {
char key[1000][1000];
int value[1000];
} Map;
int getHash (char key[]) {
int res = 1;
for (int i = 0; i < strlen(key); ++i) {
res *= key[i] - ' ' + 1;
res %= 997;
}
return res;
}
void map_put (Map *map, char key[], int value) {
int hash = getHash(key);
strcpy(map->key[hash], key);
map->value[hash] = value;
}
int map_find (Map *map, char key[1000]) {
return map->value[getHash(key)];
}
void map_remove (Map *map, char key[1000]) {
int hash = getHash(key);
map->value[hash] = -1;
}
Map initMap () {
Map map;
for(int i = 0; i < 1000; ++i) {
map.value[i] = -1;
}
return map;
}
int main(void){
Map map = initMap();
printf("%d\n", map_find(&map, "test"));
map_put(&map, "test", 10);
printf("%d\n", map_find(&map, "test"));
map_remove(&map, "test");
printf("%d\n", map_find(&map, "test"));
}
選択課題F
内田に対応する選択課題:PCIバスの概要と、現代のパソコンにおいて果たす役割を調査し、説明してください。加えて、PCIバスに接続されたデバイスをすべて列挙する方法を説明してください。
PCIバスは、マザーボードと周辺機器を繋ぐデータ伝送路です。拡張カード接続の事実上標準として普及しており、現代のパソコンでは、GPUやネットワークカードなどの主要部品が後継で互換性のあるPCI Expressによって接続されます。高速でデータ転送量も大きく、バス調停機能があるためデバイスの接続がボトルネックになりません。
PCIデバイスとCPU間の通信は必ずホストブリッジを通過するので、バス0上のデバイス0のヘッダタイプを読み取ります。各デバイスのファンクション0のベンダIDが0xffff以外の場合は実際にデバイスが接続されていることが分かるので、それを列挙します。ただし、2つのPCIバス同士を繋いだPCI-PCIブリッジの場合はセカンダリバスに対しても同様の処理を行います。
参考文献: https://docs.oracle.com/cd/E24845_01/html/E22201/hwovr-25520.html https://e-words.jp/w/PCIバス.html http://mikilab.doshisha.ac.jp/dia/monthly/monthly05/20050920/oguni.pdf
この記事が気に入ったらサポートをしてみませんか?