UEFI ELFローダーを作る 前編(Zigの紹介)

これは東京高専プロコンゼミ① Advent Calendar 2020 22日目の記事です。

導入

自作OSを始めるためには、はじめに一山超えなければなりません。 その山とはブートローダーです。legacy BIOSであっても、UEFIであってもまずはじめに書くのは自分のOSをロードするためのブートローダーなのです。

このブートローダー、OSを作りたいと意気込んでいる人にとってはちょっと厄介です。なぜなら、ブートローダーはOSほど魅力的なものではなく*1、その割にAPIについて調べたり思いの外手間がかかるからです。 そしてUEFIでのブートローダーの書き方について、UEFIアプリを書いたことがない人でも分かるように説明されている記事があまりないようでした。

そこでこの記事ではUEFIでELFファイルをロードするブートローダーの書き方について見ていこうと思います。時間がなかったので、記事を前後編に分けて前編である今回は、Zigの紹介パートとします。

今回、ブートローダーを作るにあたっては、C言語ではなくZigという言語を用いました。この言語は、C言語を置き換えることを目的とした言語であり、C言語と比べて安全なプログラムが書けるようにデザインされています。システムプログラミングや組み込みプログラミングで嬉しい機能も標準で組み込まれています。

ziglangについて

ziglangは、シンプルで安全なプログラミング言語で現在活発に開発されています。システム開発や組み込み開発向けのライブラリや機能も充実しており、UEFI APIにも対応しています*2

ziglang.org

なぜziglangを使うのか

ziglangは、C言語の置き換えとして使うことを推奨しています。このことは、zigコンパイラがCコンパイラを含んでいることからもわかります。C言語は、とても危険な言語です。例えば、以下のコードには潜在的なバグが幾つか有りますが気づけますでしょうか。

gist.github.com

yuki/Akagi :) ./a.out
please input number: -9
zsh: segmentation fault (core dumped)  ./a.out

ひとつは、よくあるバグなので見つけやすいでしょう。そうです、scanfの引数に変数のポインタではなく、変数そのものを渡してしまっているため、不正なアドレス参照が起きてセグメンテーション違反となりました。直したコードが以下です。しかし、まだバグがあります。確認してみましょう。

gist.github.com

yuki/Akagi :) ./a.out
please input number: -9
v: -9, data: 65535

dataの値が変わってしまいました。理由はわかりますでしょうか。フォーマット指定子がdなのにshortのポインタを渡してしまっていますね。結果、buffer over runが起きてスタック上の隣の変数まで書き込んでしまうことになります。このバグは、gccでwarningを表示するようにすれば検出することができますし、考えればわかることですが、そもそもこんなコードを意図して書いていたら相当ヤバイと思うので、どうせならコンパイルエラーにしてほしいと思うのです。

yuki/Akagi :) gcc -Wall test.c
test.c: In function ‘main’:
test.c:10:13: warning: format ‘%d’ expects argument of type ‘int *’, but argument 2 has type ‘short int *’ [-Wformat=]
   10 |     scanf("%d", &v);
      |            ~^   ~~
      |             |   |
      |             |   short int *
      |             int *
      |            %hd

以上のコードと同じ入出力を行うプログラムをzigで書くと以下のようになります。

gist.github.com

いくつか特徴をピックアップしてみましょう。

pub fn main() anyerror!void {
    const stdin = std.io.getStdIn();
    var v: u16 = undefined;
    const data: usize = 80;

zigでは、変数の宣言時には初期値を設定することが強制されています。これにより、初期値の設定し忘れによるバグを埋め込む余地がありません。また、次に詳しく述べますが標準入出力関数として特別なものは用意されておらず、標準入出力は単なるファイルとして扱います。std.io.getStdIn()で標準入力ファイルを取得できます。特に初期値がない場合には、undefinedで初期化することができます。undefinedで初期化した変数に何も代入しないまま使用するとそれはバグとなります。zigでは、debugモードにおいてundefinedで初期化すると0xaaが書き込まれるようになっています。これにより、早期にバグを検出することができます。

    std.debug.warn("please input number: ", .{});
    v = read_num(u16, &stdin);
    std.debug.warn("v: {}, data: {}\n", .{ v, data });
}

先程少し書きましたが、zigでは標準入出力を特別に抽象化していません。標準入出力は、zigの標準ライブラリにあるAPIを使ってユーザーの責任において行う必要があります。今回はお試しコードなので出力はstd.debug.warn関数を用いました。これは、debugモードにおいてのみ有効なものです。入力はデバッグモードだけで使えるようなものもないのでお試しであっても自分で書かなくてはなりません。

fn read_num(comptime T: type, stdin: *const std.fs.File) T {
    var buf: [64]u8 = undefined;
    const len = stdin.read(&buf) catch |err| {
        std.debug.warn("Error while reading number: {}\n", .{err});
        std.os.exit(1);
    };
    if (len == buf.len) {
        std.debug.warn("Input is too big!\n", .{});
        std.os.exit(1);
    }
    const line = std.mem.trimRight(u8, buf[0..len], "\r\n");
    const val = std.fmt.parseInt(T, line, 10) catch |err| {
        std.debug.warn("Error while parsing number: {}\n", .{err});
        std.os.exit(1);
    };
    return val;
}
fn read_num(comptime T: type, stdin: *const std.fs.File) T {

関数宣言です。comptimeを使ってジェネリックプログラミングができます。

var buf: [64]u8 = undefined;

zigの配列型は、要素数ごとに固有の型になっています。つまり、[64]u8のbufと[128]u8のbufは別物です。もし、配列外参照をコンパイル時に検出した場合にはコンパイルエラーとしてくれます。さらに、コンパイル時に検出できなかった配列外参照についてもデバッグモードの強力なランタイムにより検出することができます。このランタイムは、@panic関数を自分で実装しさえすればベアメタルにおいても使用することができます。

./main.zig:5:8: error: index 65 outside array of size 64
    buf[65] = 'a';
index out of bounds
/home/yuki/workspace/tmp/zig-test/src/main.zig:33:9: 0x22cdea in main (zig-test)
    hoge[v] = 'a';
pub fn panic(msg: []const u8, error_return_trace: ?*builtin.StackTrace) noreturn {
    @setCold(true);
    EFI.puts("PANIC: ");
    EFI.puts(msg);
    EFI.puts("\r\n");
    while (true) {}
}
    const len = stdin.read(&buf) catch |err| {
        std.debug.warn("Error while reading number: {}\n", .{err});
        std.os.exit(1);
    };
    if (len == buf.len) {
        std.debug.warn("Input is too big!\n", .{});
        std.os.exit(1);
    }

read関数では、bufferの大きさを超える入力を受けないようになっています(先述のように、配列型はその要素数を持つので、buf.lenによってbufのサイズを得ることができます)。

    const line = std.mem.trimRight(u8, buf[0..len], "\r\n");
    const val = std.fmt.parseInt(T, line, 10) catch |err| {
        std.debug.warn("Error while parsing number: {}\n", .{err});
        std.os.exit(1);
    };

あとは、入力を整数にパースします。これは標準ライブラリで行うことができます。

さて、長くなってしまいましたが一通りZigの紹介をしてきました。Zigはシンプルでありながら、とても強力にプログラマーのサポートをしてくれる言語です。ドキュメントが不十分なので、今の所自分で標準ライブラリを見に行って仕様を調べたりする必要がありますが、discordで質問をすると開発者のみなさんがすぐに回答してくれます。今後の推移に期待しましょう。

では、次回は実際にローダーについて解説します。

*1:諸説あります...

*2:全部実装されているわけではありませんが、ブートローダーに必要な部分は一通り私が書いておきました

CPU自作のためのコミュニティを設立した

あけましておめでとうございます。新年はいかがお過ごしでしょうか。 私は元旦に初日の出をみたりとか、年賀状の作成に追われる年末を過ごしたりするわけでもなく例年より素っ気ない新年を迎えています。

さて、本題です。 先日、自作CPU仲間であるCra2yPierr0t氏と自作CPUにおけるI/Oについて考えるため研究会をしました。 その中の会話で、「やっぱり自作CPUもosdev-jpみたいなコミュニティがある嬉しいねー」という話になりタイトルの通り設立する運びとなりました。

twitter.com

そんなわけでその日のうちにslack workspaceを作り、先程宣伝のツイートをしたところ10人以上の方にご参加いただけました!ありがたい。

ところでこういうslack workspaceを作ったはいいものの、みんなが自発的に会話をするようにならなければ意味がありません。 積極的に話題を作ってもらうにはどうしたらいいのでしょう。難しいです。

また、CPU自作もくもく会も計画しています。

参加したい方は以下のリンクから参加できます。

join.slack.com

よろしくおねがいします。

シリアル通信をハードウェアレベルで実装した

これは東京高専プロコンゼミ① Advent Calendar 2019 20日目およびOS-CPU Advent Calendar 2019 20日目の記事です。

遅刻しました、ごめんなさい!! そして予定していたテーマからも変わっています。。。お許しを。

言い訳

もともとこの記事のネタは「EFI ELFローダーを作る」の予定でした。今流行りのzen言語を使って作るぞ〜とウキウキしていたのですが、zen言語(zig言語)でサポートされているUEFI APIに誤りや未実装箇所があることが判明したためまずはそちらを修正・追加することから始めていまして時間がかかってしまっています。 一応進捗として、zig言語にPRを送って見事マージされました。やったね。

シリアル通信とは

シリアル通信とは一本の伝送路で一つずつビットを送ることで行うエレクトリカルコミュニケーションです。 シリアル通信といってもいろいろなものがありますが、私が実装したのはUART(Universal Asynchronous Receiver/Transmitter)です。UART以外には、SPIとかEthernetとかUSB(Universal Serial Bus)などもシリアル通信の一種です。

ここでAとBという2つのコンピュータでUART通信することを考えると、Aの送信ポート(TX)とBの受信用ポート(RX)、Aの受信ポート(RX)とBの送信ポート(TX)の計2本を接続する必要があります(実際にはGNDも接続しますが)。 2本の送受信用ケーブルがあるので全二重通信というように呼びます。

UART通信をする際には以下の項目について通信する2つのコンピュータ間で共通の設定をする必要があります。

  • baud rate
  • stop bit
  • data bit
  • parity
  • hard ware flow control

私は以下のように設定しました。

  • 115200bps
  • 1bit
  • 8bit
  • none
  • none

作り方

ソフトウェアでUARTを使うときには設定用レジスタにパラメータをいれて割り込み設定して〜ってかんじだと思いますがハードウェアでやるにはもうちょっといろいろ考える必要があります。 大変なことの一つとして、UARTはクロックを共有しない非同期通信なので位相のずれを考慮する必要があります(周波数は、事前に合わせてあるものとします)。

ここでは概要だけ説明します。

まず送信側ですが、これはやるだけです。FPGAのクロックをUARTのボーレートに分周してあとはそれに合わせてスタートビットとデータとストップビットを送るだけです。 次に受信側ですが、こちらはUARTのボーレートより何倍か早めの周波数でRXを見てあげて、複数回0がきたらそれをスタートビットと認めあとは読んでいく感じです。

f:id:yuhki0223:20191225001619p:plain 送信の様子

f:id:yuhki0223:20191225001632p:plain 受信の様子

すごく適当ですが、アドベントカレンダーなので許してください。 実装したものをGitHubに公開してあります。興味のある人は読んでみてください。

github.com

プロコンゼミ ネットワーク講習会を開催します!

この記事は東京高専プロコンゼミ① Advent Calendar 2019の2日目の記事です。

今日まで中間試験お疲れ様でした。残り3週間くらい授業を受ければ冬休みになって、もう2020年が訪れます。早いなあ。

記事のタイトルにもあるように来る2019年12月19日、プロコンゼミの成員に向けてネットワーク講習会を開催したいと思っています。 ここでいうネットワークはコンピュータネットワークのことです。

例えば、このブログのURLをブラウザに入力すると当然のことながらこのブログが表示されます。コンピュータに普段から触れている皆さんであれば、URLから直接ブログのあるサーバーへアクセスできるわけではなく、ネームサーバーからURLに対応するIPアドレスを取ってきて、そこへアクセスすることでブログのあるサーバーへアクセスできる、ということはなんとなく知っていると思います。しかし、IPアドレスがあったとてIPv4であれば232パターン(約43億)もある膨大なアドレスの中からどうやって(ある程度の速度で)目的のアドレスへたどり着くのでしょう。

講習会では以上の例はもちろん、実際によくみるイーサネットケーブル(ツイストペアケーブルとか呼びます)を作ってみて我々が何気なく使うネットワークも結局は一本一本の導線(光ケーブルを使ったり、電波を使ったりすることもありますが)を通って上流のスイッチやルーターのLEDをピカピカ光らせながら目的地点までたどり着くということを体感してもらったり、ここまで辿り着けるかはわかりませんけれど、ネットワークのトラフィックがどのように捌かれるのかというところまで触れたらいいなあと思ってます。

どうしていきなりこんな講習会をやろうと思ったか、動機はざっと以下の通りです。

  • プロコンで他の講習会も含めて色々開いたら面白そうなので、そのきっかけにしたい
  • 部室で度々起きるネットワークインシデントの重大さを理解してほしい
  • 部室のネットワーク環境を維持できる人材を育成したい
  • ネットワークの面白さを知ってほしい

講習会はとりあえず1回開いてみて、希望があれば続編もやろうと思います。 ネットワークに詳しい人も呼んでます。疑問があるならたくさん質問を投げてみてください。

それでは、乞うご期待!

KLab Expert Campに参加した

夏休みが終わってしまいました。休み明けの学校というのは本当に辛いもので先週はずっと瀕死の状態だったのですが、そろそろ回復してきたのでこの記事を書いています。

KLab Expert Campとは

ラブライブ! スクールアイドルフェスティバルを起動したときに出てくるあのKLabが主催する技術系インターンの特別版です。 今回が初めての開催のようで、「TCP/IPプロトコルスタック自作開発」がテーマでした。 講義ベースでプロトコルスタックの実装に関する知見を深めるコースと実装ベースで発展的なテーマに取り組むコースの2つが用意されていて、自分は後者で参加しました。

やったこと

実は自分は参加初日に実装ベースのコースに配属されていたことを知ったので、当日の思いつきでRIP(Routing Information Protocol)をmicropsの上で実装することにしました。 実はこのKLab Expert Campの前の週に先輩からルーティングのいろはを教えてもらっていたのでその影響がかなりあったと思います。 4日間だけでの突貫実装でしたが、講師陣の方々に質問しまくりながら最終日にはそれっぽいルーティングができるように仕上がりました。

スライドも公開してみたのでよければ見てください。

www.slideshare.net

開発風景

感想とか

先週のセキュリティキャンプに参加したときにも思ったことですが、気軽に質問できる環境っていいなーと思いました。 質問することで、自分がどこまで理解できているのかちゃんと把握できるし、わからないことがわかるし、質問したこと以上の付随知識がもらえることもあるので本当に美味しいです。

あと、4日間本当に集中して取り組むことが出来ました。家の部屋だとこうはいかないのでやっぱり環境って大事だなあと思います。 環境に関して、まずオカムラの椅子が最高でした。そして昼食がとても美味しかったです。さらに、ルーティングプロトコルデバッグ用に対向用のスイッチやルーターも用意してもらえてトリプル役満でした。

懇親会のときにネットワークのアカデミックな話が聞けたのもとても良かったです。

懇親会とお弁当

(奥の方にスイッチが写ってる)

楽しい4日間でした。ありがとうございました。

PS. KLabの読み方は、「クラブ」らしいです(ずっと「ケーラボ」って読んでた...)

セキュリティ・キャンプ全国大会2019に参加した

タイトルの通りなのですが、セキュリティ・キャンプ全国大会2019を修了したのでその参加記的なのを書いていきます。 前に応募用紙晒しをしたときにも書きましたが私はYトラックのOS開発ゼミのフルスクラッチOSを書こう!というテーマで参加しました。 集中開発コースなのでずっとOSを開発してたわけですが、OSの機能など細かい解説は復習も兼ねてじっくりとやっていきたいので追々scrapboxのほうにまとめていきます。この記事は開発日誌的なものだと思っていただければ良いと思います。

1日目

1日目は顔合わせの日なので開発はしませんでしたが、特別講演やLT大会、それとグループワークがありました。 余談ですが、実はこの日お昼くらいから偏頭痛をこじらせていて、ずっと痛い頭を抱えていたので何があったのかよく覚えていません。悲しい。こんなことにならないようにキャンプ前日はちゃんと休みましょう。

2日目

2日目は開発時間が一番長い日でした。

午前中はuchan先生つきっきりでOSのデバッグをしていました。

バグの内容は割り込みハンドラの設定後、割り込みがあると再起動してしまうというものでした。再起動の直接的原因はトリプルフォルトというもので、x86の場合ダブルフォルトまでであればダブルフォルト例外を発行しますが、トリプルフォルトの場合は再起動します。おそらく目的の割り込みハンドラだけでなく、例外ハンドラも正しく設定できていないためトリプルフォルトとなっているのだろうと検討をつけ、まずはIDTを設定するコードにバグがないか静的解析を試みました。しかし問題がなさそうに見えたので、今度はsidt命令を使って登録したIDTRやディスクリプタが正しいか確認したところ、ディスクリプタに登録したハンドラ関数のアドレスが正しくないことが判明。実はこの事象、数日前に同じくOS開発ゼミに参加していた突撃隊さんも遭遇していたものを踏んでいたことがわかったのです。結論としてはコンパイルオプションに-fno-picをつければ解決するということだったのですが、もっと詳しく知りたいという方はこちらをご覧ください。

バグが取れてうれしい私↓

例外ハンドラが正しく登録出来たことでデバッグもしやすくなりました↓

そして午後からはメモリ管理をしてみようと思い勉強や実装を始めました。メモリ管理をするためには、メモリマップを知らなければなりません。メモリマップはUEFIのBoot ServicesのgetMemoryMap()によって取得できます。

上記の通りメモリマップを取得するプログラムを書いていたのですが、ここで「配列の先頭アドレスのアドレス」を渡さなければいけない箇所を誤って「配列の先頭アドレス」を渡してしまっていたが為に、次の日の午前まで時間を溶かしてしまいました。

3日目

この日は寝坊して、IPAの方と看護師さんが起こしにきました。本当に申し訳ないです。

起床技術者試験に落ちた後、朝食抜きで始まった開発ですが午前中は先程言ったバグのデバッグをチューターのPG_MANAさんとやっていました。C言語はもう少し人間に優しくなってほしいです。

同じくOS開発ゼミに参加していて、Rustで組み込みOSを自作していたikubakuさんからこんなこんなお言葉を頂きました↓

取得できたメモリマップ↓

午後は取得できたメモリマップをもとにメモリ管理を実装していくのですが、ページングを利用しているOSではまずページ単位でメモリの割当をするページフレームアロケーターを使い、その中でmalloc()などが細かくメモリの割当をするということがほとんどなそうなので私もそれにならうことにしました。

せっかくページフレームアロケーターを実装するのであればページテーブルの設定も出来たほうがいいと思い、PG_MANAさんに教えてもらいながらページテーブルの設定をしました。

この日の開発は夕食前までで、夕食後は企業紹介やグループワークがありました。

4日目

4日目はしっかり6:30に起床し朝食にありつくことができました。

そして午前は3日目に設定したページテーブルに合わせて空き領域を4KiBにアラインメントしページフレームのブロックを作りました。

また、簡単な実装ではありますがページフレームアロケーターも午前中にできました。

Yトラックでは昼食後に成果発表会を行うことになっていたので、午後はその準備をしました。 発表時間は一人2分ととても少なく、あまりいい発表が出来ずお見苦しいところをお見せしてしまいました。

発表会が終わってから夕食まではとりあえず今まで実装してきた機能がすべてちゃんと動作するか確かめてみようと思い、コメントアウトしていた関数をすべてもとに戻し動作確認してみたところ、シリアル通信がqemuでは動くものの実機では正しく動いていないことがわかりそのデバッグをしました。

しかし原因はよく分からずそのまま夕食、企業紹介、グループワークへ。

シリアル通信の設定が悪いのかなと思い、シリアル通信に詳しそうな坂井弘亮師匠に見てもらったところ、コンパイラの最適化でシリアル通信の送信が可能かどうか判断する関数の呼び出しが、1回しか行われていない(ソースコード上ではbusy loopで呼び出してる)のではないかというアドバイスを頂きました。

そこでコンパイルオプションに-O0を追加し動かしてみたのですがこれでもまだ動かず。 講師のuchan先生にも見てもらい、最終的に原因はアセンブリで定義していたinb()関数が間違っていたことであることがわかりました。悲しい。

5日目

5日目は最終日です。他のトラックも含めた成果発表を聞きました。 井上root取っ太郎が面白かったです。

全体を通しての感想

色んな人が自分のOSのデバッグを手伝ってくれるのが本当に心強いなと思いました。こんな機会なかなかないです。

今までは30日OS自作本やブログ記事、同人誌を見て写してただ動作を確認してみるということが多かったのですが、キャンプではオリジナルなコードもたくさん生やせてやっと自分でOSを作るということがわかった気がします。

5日間お疲れ様でした。

6日目?

7日目??

セキュリティ・キャンプ全国大会2019へ参加することになった(応募用紙晒し)

中間試験が一段落したので少し出遅れた感はあるけれど、この記事を書いています。

題名のとおりセキュリティ・キャンプ全国大会2019のシステムプログラミングトラックOS開発ゼミに参加することになったので、恒例の応募用紙晒しをしてみようと思います。 ちなみにセキュキャンに応募するのは今回が2回目です。実はリバースエンジニアリングゼミにも興味があってそちらの応募用紙も完成させてはいたのですが、最終的にOS開発ゼミのほうで提出することにしました。

あらためて自分の応募用紙を見直してみると結構はずかしいです。そういえば書いている最中も自分の文章にあまり自信がもてなくて何回も消したり書いたりしてたなあなんて思いだしました。

以下で掲載している応募用課題はこちらで公開されています https://www.ipa.go.jp/files/000073173.txt

セキュリティ・キャンプ全国大会2019のホームページはこちら https://www.ipa.go.jp/jinzai/camp/2019/zenkoku2019_index.html

応募用紙

  • 共通問題A
我々講師は、普段いくつかのOSを使っていますが、使い込むうちに色々な発見をします。
皆さんもきっとそういう体験があると思います。
あなたが普段使っているOSで、好きな機能と改善してほしい部分について、思いのたけを聞かせてください。
この問では、皆さんが普段どの程度興味を持って既存OSを観察しているかを評価します。

私が使っているOSで好きな部分は、OSのソースコードが大変に簡潔に記述されていること、そして余計な機能を一切入れないこと、またそれらによってOSに存在する脆弱性を限りなく少なくすることを目的にしていることです。 このOSのソースコードは本当にびっくりするくらいにきれいです。私はOSというものにそこまで深く触れたことがなく、C言語C++でのプログラミングを少ししたことがある程度なのですが、それでも他のOSのソースコードを読もうとしたときより「これは楽に読めるぞ」と感じたのでトリッキーなコードが少なく素直なのだと思います。また、余計な機能を一切入れないこともコードの単純化に寄与しています。普段ほとんどの人が使わないような機能のためにOSの開発がより困難なものになってしまうのは私は良くないと思います。このようにOSの構造を簡潔に、わかりやすくすることで見通しを良くすることに私はとても共感しています。 しかし、これらは決していいことづくしというわけではありません。このOSはソースコードの単純さや余計な機能を一切入れないことによってパフォーマンスを犠牲にしています。ハードウェアの性能向上を待てばパフォーマンスは良くなると思いますが、ハードウェアの性能向上にそこまで期待していいのかという問題もありますから、なかなか難しい問題だなと思います。

  • 共通問題B
皆さんが仮にOSを作るとしたら、「どんなOS(やOSの機能)を作ってみたい」でしょうか?
(既にOSを作った事がある人は、その特徴を書いてくれても構いません。)
そして、なぜそれを作ってみたいと思ったのでしょうか?
皆さんが心の中で夢描いているであろう、ワクワクするようなOS像を教えてください。
※「Linux開発者を目指そう!」テーマを受講したいと思っている方は「どんなLinuxカーネルの機能を作ってみたいか」を答えてください。
※「Raspberry Pi向け組み込みOSを作ろう!」テーマを受講したいと思っている方は「どんな組み込みシステムを作ってみたいか」を答えてください。

Linuxでは現在Linux向けにコンパイルされたプログラムしか実行することができなかったと思いますが、他のOS向けにコンパイルされたプログラムを動かすことができるバイナリエミュレーションの機能をつくってみたいです。 動機としては、この機能が特別ほしいなと思ったというわけではなく、単に実装してみたいなと思ったからです。私は数多くあるOSの機能のうちユーザーアプリケーションを実行する機能が好きです。もともと私がOSに興味をもったきっかけが、自分の書いたプログラムがどのように動いているのか知りたかったことにあるのが影響しているのかもしれません。ユーザープログラムを実行するに際してはいろんなOSでいろんな工夫がされているなと思います。例えば、LinuxにはVDSOというものがありますが、これはシステムコールはkernel側で処理されるものだという常識を覆すおもしろい発明だなと思います。

  • 共通問題C
C言語で双方向リンクリストとそれを操作する関数を作り、ソースコードを提出してください。
  リンクリストを生成する関数、要素を任意の場所に挿入する関数、全ての要素を順に標準出力に印字する関数、の3つがあれば十分です。
  やる気があればもっとたくさんの機能を実装しても構いません!
#include <stdio.h>
#include <stdlib.h>

int init(void);
void end(void);
struct node * search_tail(void);
int insert_tail(int value);
void delete_tail(void);
int insert_index(int value, unsigned int index);
void print_list(void);

struct node {
    int value;
    struct node *next;
    struct node *prev;
};

struct node *head;

int
init(void)
{
    head = malloc(sizeof(struct node));
    if(head == NULL) return -1;
    head->value = 0;
    head->next  = NULL;
    head->prev  = NULL;
    return 0;
}

void
end(void)
{
    struct node *tail = search_tail();
    while(tail != head) {
        delete_tail();
        tail = search_tail();
    }
    free(head);
    return;
}

struct node *
search_tail(void)
{
    struct node *search = head;
    while(1) {
        if(search->next == NULL) return search;
        search = search->next;
    }
}

int
insert_tail(int value)
{
    struct node *ins;
    struct node *tail = search_tail();
    
    ins = malloc(sizeof(struct node));
    if(ins == NULL) return -1;
    
    ins->value = value;
    ins->next = NULL;
    ins->prev = tail;
    tail->next = ins;
    return 0;
}

void
delete_tail(void)
{
    struct node *tail = search_tail();
    if(tail == head) return;
    tail->prev->next = NULL;
    free(tail);
    return;
}

int
insert_index(int value, unsigned int index)
{
    unsigned int counter = 0;
    struct node *current = head;
    struct node *ins;

    ins = malloc(sizeof(struct node));
    if(ins == NULL) return -1;
    
    if(index < 0) return -1;
    while(counter < index) {
        if(current == NULL) return -1;
        current = head->next;
        counter++;
    }
    if(current == NULL) return -1;

    ins->value = value;
    ins->prev  = current;
    ins->next = current->next;

    current->next = ins;
    return 0;
}

void
print_list(void)
{
    struct node *current = head->next;
    while(current != NULL) {
        printf("%d\n", current->value);
        current = current->next;
    }
    return;
}

int
main(int argc, char *argv[])
{
    if(init() < 0) return -1;
    if(insert_index(5, 0) < 0) puts("error");
    if(insert_tail(6) < 0) puts("error");
    if(insert_index(3, 1) < 0) puts("error");
    print_list();
    end();
    return 0;
}
設計・実装で工夫した点を述べてください。

整数型の符号の有無や関数の引数などを最小限に抑え、簡潔な実装を心がけました。また、メモリリークなどのバグがないようエラーチェックをしっかりと行ったつもりです。

  • 選択問題S3
Linuxカーネルについて知りたいこと、それについてこれまで調べたこと、
つまづいたことを教えてください。最終的に解決しなかったとしてもOKです。
技術力が優れているかではなく、どれだけ試行錯誤したかという観点で採点をします。
「この機能のこのコードの意味がわからなかった」という高度なものでもいいですし、
「そもそも何から手を付けていいのかもわからなかった」というものでも構いません。

共通課題でも述べたのですが、私はプログラムを実行する仕組みに興味があるのでそれに関連するコードを少しだけ読んだことがあります。そこで不思議に思ったことなのですが、linuxのローダーの実装はfsというディレクトリの下に配置されています。fsというのはおそらくfilesystemのことをさしているのだと思いますが、自分にはこの理由がよくわかりませんでしたし、調べてもこれについて述べているものは探した限りなかったです。また、実際にLinuxにコントリビュートするとして、どういう機能を実装するかというアイデアをどうやって思いつくのか知りたいです。Linuxは多くの優秀な人がコントリビュートしていると思いますが、そのなかで必要とされる実装をどうやって生み出すのか私には全然分かりません。

  • 共通問題D
その他、書ききれなかったことを好きなだけ書いてください。

いままで自分一人では解決できなかった疑問をこの機会にぜひ解消していきたいです。そして、自分もLinuxや他のOSも含め貢献出来るような人になれるように努めていきたいです。