Hatena::ブログ(Diary)

七誌の開発日記(旧) このページをアンテナに追加 RSSフィード

新ブログ Twitter OneDrive Wiki

2011-05-06

[][][]構造を表示

id:n7shi:20101204ファイルシステム読み込みツールを改造して、ディレクトリやファイルの構造が表示できるようになりました。今まではイメージ全体をZIP圧縮して取り出すことしかできませんでしたが、ファイル単位で取り出せるようになりました。Windows FormsとSilverlightでほぼ同じGUIを実装しました。

現時点では読み込みしかできません。将来的には書き込みをサポートして、逆アセンブラインタプリタと統合すれば面白いことになりそうです。

2011-05-02

[][][][]名古屋Geek Bar LT

名古屋Geek Bar 5月2日(月)でLTをして来ました。V6関係のツールがメインですが、自己紹介に絡めて独自言語のセルフホスティングも取り上げています。

SlideShareレイアウトが崩れないようにPDFをアップしています。PowerPointのデータはこちらです。

USTREAM中継の録画も配信中です。

取り上げた話題については以下を参照してください。

2011-04-08

[][][][]コンパイラが動作

id:n7shi:20110330で開発に着手したPDP-11のインタプリタですが、最低限必要な命令とシステムコールを実装して、ようやくV6コンパイラが動くようになりました。Silverlightに対応した環境ではブラウザ内で動きます。

このままでは実際の作業には使えないため、Silverlightから出してコマンドライン上で動くようにしたいと思います。

2011-03-30

[][][][]インタプリタ

id:n7shi:20110322で開発したPDP-11の逆アセンブラを拡張して、UNIX V6のバイナリを対象としたインタプリタの開発に着手しました。まだ未実装の命令やシステムコールが多数ありますが、とりあえずprintf()くらいは動くようになりました。Silverlightに対応した環境ではブラウザ内で動きます。

もともとC#で作っていましたが、最近VB.NETに慣れてC#より快適になってきたため、VB.NETで書き換えました。

2011-03-22

[][][][]逆アセンブラ

PDP-11の命令について調査するため、Silverlightで逆アセンブラを作成しました。UNIX V6のa.outに対応しています。

Lions本では8進数に戸惑ったため、デフォルトの出力は16進数です。8進数に切り替えることもできます。

2011-01-15

[][][]初級勉強会

※地震の影響による電力・交通事情を踏まえ、中止しました。

まだ少し先ですが、Silverlightの初級勉強会を開催することになりました。初心者を対象としていますので、開発は初めてという方でもお気軽にご参加ください。

対象言語はC#とVB.NETです。お好きな方をお選びください。

2010-12-26

[][][]言語変換でいきなり実用を目指す

※このエントリは F# Advent Calendar jp 2010 第17回目の参加記事です。

F#の話題を目にしても「何やら難しそうなコードが掲載されていて、自分には関係なさそうだ」と素通りしたことはないでしょうか?実は、私もそうでした。F#の本を入手してぱらぱら眺めてから、2年近くまともに使わずに放置しました。

ところでよく「C#とVB.NETは文法が違うだけで中身はほぼ同じ」と言われます。F#もあまり関数型の側面を強調しないで、VB.NETと同列に捉えてみるのも一つの手です。そんなわけで、C#使いの方へF#変換プログラムのクリスマスプレゼントです(間に合いませんでしたが・・・)。

何だこれ、C#で書かれているじゃないか!F#のエントリとしては画竜点睛を欠くんじゃないか? ―― いえ、ちょっと待ってください。

C#からF#に変換できるんだから、自分自身を変換してしまえば済みます!

というわけでこちらが本物(?)の、C#からF#に変換するプログラムです。Silverlight化したためブラウザ上で実行できます。

本来Visual Studio上でF# Silverlightプロジェクトを作成するにはVisual Studio 2010 Professional以上が必要ですが、今回はid:n7shi:20100710の方法によりフリーのVisual Web Developer 2010 Expressで作成しました。

余談

言語処理系は自分自身を処理(いわゆるセルフホスティング)できることが望ましいと思い、変換プログラムはC#自身で書きました。しかしこの方法論では新言語の開発で卵と鶏問題が発生します。対処方法として、まず既存の言語で新言語(最低限の言語仕様)から既存の言語への変換プログラムを実装して、次に本番の処理系を新言語自身で実装するという方法があります。後者の実装度が前者を追い抜けば、以後は変換なしで自分自身を処理できます。この方法の例として、SqueakはC言語へのトランスレータから出発したそうです。

制限事項

どんなC#のコードでも変換できるわけではありません。

  • ループ中での break, continue は使用不可
  • for は使用不可
    • foreach は使えるため以下で代用
    • foreach (var i in Enumerable.Range(0, 100))
  • return で関数を途中で抜けるのは不可
    • 値を返すための return は可能。分岐がある場合、それぞれの分岐の最後でreturnする。
  • メンバへのアクセスは必ず this. を経由して行う
  • C# 3.0のラムダ式は使用不可
    • C# 2.0のdelegateによるクロージャは使用可能
  • フィールドの初期値は定義不可
  • ++, += のように直接数値を書き換える演算子は使用不可
    • a = a + 1; などで代用
  • ローカル変数の宣言では必ずvarを使用(型推論必須)
  • (その他多数)

変換プログラム自体、これらの制限事項を踏まえて記述されているため、自分自身の変換(セルフホスティング?)ができるというカラクリです。

いきなり実用を目指す

話を戻します。C#とF#で同じものが表現できるのなら、文法さえどうにかすればC#の代用としてF#を使い始めるというのも決して難しいことではありません。その一助として、今回のプログラムがお役に立てば幸いです。

とりあえずF#らしさとか機能とかは棚に上げ、まずは実用を目指して使い始めながら、徐々にF#らしい使い方を広げていけば良いのではないでしょうか・・・という甘いストーリーです。

しかしF#では意図的にフロー構造が制限されているため、C#と1対1でコードを置き換えることができません。いわゆる関数型の考え方に沿ったコードを書いてもらうためにこういう制限があります。しかしこれも最初のうちは関数型がどうこうという小難しいことは棚に上げ、単純に機能が制限されたと捉えて、フローを工夫してみる所から始めるのもアリだと思います。具体的には、上の変換プログラムの制限事項が、この事情を反映しています。

参考資料など

実は変換プログラムを作る前から、同じような発想でC#を手動変換しながらF#を使っていました。当時のメモをまとめて、C#とF#を対訳にしたものを公開しています。

ちなみに手動で変換した最大のものはid:takuto_hさんの試作言語Yellowです。 (⇒ id:n7shi:20090720

変換をしているうちにコツを覚えたので、段々とスクラッチから書けるようになってきました。この過程が私の考えている『いきなり実戦投入しながら慣れる』というイメージです。

まとまりがなくなりましたが、この記事が皆さんのF#ライフのきっかけになれば、これほど嬉しいことはありません。

2010-12-04

[][][]ファイルシステムの読み込み

f:id:n7shi:20101205100253p:image:right

id:oraccha:20101101の手順を参考に、UNIX V6をSIMHで動かしてみました。分析のためファイルを取り出そうとしたのですが、TCP/IP以前のOSのためネットワークが使えるのか不明で、ディスクイメージからファイルを取り出す方法も分かりません。仕方ないのでカーネルのソースを読みながらファイルを取り出してみました。

読み込みツールはF#で実装しました。ブラウザ上から実行できるようにSilverlight化しました。id:n7shi:20101004で作成したZIP圧縮コードにより、ファイルシステム全体をZIPファイルとして保存することができます。

【追記:2015.11.12】ローカルで動かすGUI版もあります。(Silverlight非依存)

以下、UNIX V6のC言語ソースを引用しながら簡単に説明します。ソースコードはタブで整形されていますが、レイアウトが崩れるのを防ぐためスペースに置換して引用しました。タブは8文字を想定しているようです。

構造

前掲の図がディスクイメージの構造です。左の番号はブロック番号で、1つのブロックは512バイトです。ブロックは現在セクタと呼ばれている概念と同じもののようです。最初のブロックはMBRと書きましたが、これはx86用語で、当時どう呼ばれていたかは不明です。IPLの機械語コードが生バイナリとして入っていて、0000〜0777(0x0000〜0x01FF)番地に読み込まれて実行されるようです。

スーパーブロック

MBRの次のブロックにはファイルシステムの情報が収められ、スーパーブロックと呼ばれています。filsys構造体として定義されています。

/usr/sys/filsys.h
/*
 * Definition of the unix super block.
 * The root super block is allocated and
 * read in iinit/alloc.c. Subsequently
 * a super block is allocated and read
 * with each mount (smount/sys3.c) and
 * released with unmount (sumount/sys3.c).
 * A disk block is ripped off for storage.
 * See alloc.c for general alloc/free
 * routines for free list and I list.
 */
struct  filsys
{
        int     s_isize;        /* size in blocks of I list */
        int     s_fsize;        /* size in blocks of entire volume */
        int     s_nfree;        /* number of in core free blocks (0-100) */
        int     s_free[100];    /* in core free blocks */
        int     s_ninode;       /* number of in core I nodes (0-100) */
        int     s_inode[100];   /* in core free I nodes */
        char    s_flock;        /* lock during free list manipulation */
        char    s_ilock;        /* lock during I list manipulation */
        char    s_fmod;         /* super block modified flag */
        char    s_ronly;        /* mounted read-only flag */
        int     s_time[2];      /* current date of last update */
        int     pad[50];
};

PDP-11は16bitマシンのため、intは16bit符号あり整数型(int16_t)です。sizeof(filsys)は516バイトで、ブロック(512バイト)より大きいのですが、パディング(pad)が大雑把に定義されているだけで、実際に516バイト使われているわけではないようです。

ブロックやinodeのリストは書き込む際に必要となりますが、今回は読み込みだけを対象としているので、詳細は飛ばします。

in coreという表現がありますが、coreは今で言うメモリを指しているため、「メモリ上」という意味で使われているようです。ディスクイメージを見ると値が書き込まれているため、純粋にメモリ上だけに存在するわけではなく同期しているようです。

実際の読み込みはmain()から呼ばれるiinit()で行われています。日本語のコメントは私の追記です。

/usr/sys/ken/alloc.c
/*
 * iinit is called once (from main)
 * very early in initialization.
 * It reads the root's super block
 * and initializes the current date
 * from the last modified date.
 *
 * panic: iinit -- cannot read the super
 * block. Usually because of an IO error.
 */
iinit()
{
        register *cp, *bp;

        (*bdevsw[rootdev.d_major].d_open)(rootdev, 1); /* rootdevを開く */
        bp = bread(rootdev, 1); /* 1はブロック番号 */
        cp = getblk(NODEV); /* メモリ確保, malloc(512)に相当 */
        if(u.u_error)
                panic("iinit");
        bcopy(bp->b_addr, cp->b_addr, 256); /* memcpy()に相当, 256はワード長 = 512バイト */
        brelse(bp); /* 読み込んだブロックのデータを解放 */
        mount[0].m_bufp = cp;
        mount[0].m_dev = rootdev;
        cp = cp->b_addr; /* 確保されたメモリの生ポインタを取り出す */
        cp->s_flock = 0;
        cp->s_ilock = 0;
        cp->s_ronly = 0;
        time[0] = cp->s_time[0];
        time[1] = cp->s_time[1];
}

s_flock, s_ilock, s_ronlyは読み込み後に初期化していることから、ディスク上では同期していないようです。

inode

スーパーブロックの次にはinode(アイノード)のリストが来ます。inodeというのはファイルに対するヘッダのようなものですが、ハードリンクにより複数のファイルから1つのinodeを参照することもあるため、1対1でファイルと対応しているわけではありません。そのためinodeにはファイル名の情報が含まれていません。

inode全体で使えるブロックサイズは filsys.s_isize で示されています。1ブロックが512バイトで、1つのinodeが32バイトであることから、ファイルシステム上のinode数の上限は s_isize * 16 個となります。

inodeは1から数えます(0は「なし」を意味します)。最初のinode(inode番号1)がルートディレクトリです。inodeの抽出はiget()で行われています。ldivは除算、lremは剰余です。

/usr/sys/ken/iget.c: iget()より抜粋・追記
        ip = bread(dev, ldiv(ino+31,16)); /* (ino+31)/16 */
        ip1 = ip->b_addr + 32*lrem(ino+31, 16); /* 32*((ino+31)%16) */

inode番号2の場合、ino=2, (2+31)/16=2, 32*((2+31)%16)=32 となり、ディスク上のブロック番号2の32バイト目に存在します。

構造体

inode構造体はino.hとinode.hの2箇所で定義されていますが、ino.hはディスク上の格納形式を示すためだけに含まれているヘッダで、実際にはコードから使用されていないようです。

/usr/sys/ino.h
/*
 * Inode structure as it appears on
 * the disk. Not used by the system,
 * but by things like check, df, dump.
 */
struct	inode
{
        int     i_mode;
        char    i_nlink;
        char    i_uid;
        char    i_gid;
        char    i_size0;
        char    *i_size1;
        int     i_addr[8];
        int     i_atime[2];
        int     i_mtime[2];
};

/* modes */
#define IALLOC  0100000
#define IFMT    060000
#define         IFDIR   040000
#define         IFCHR   020000
#define         IFBLK   060000
#define ILARG   010000
#define ISUID   04000
#define ISGID   02000
#define ISVTX   01000
#define IREAD   0400
#define IWRITE  0200
#define IEXEC   0100

構造体の個々のフィールドの意味は、inode.hの方に書いてあります。i_flagなどディスク上に存在しないヘッダが付いています。

/usr/sys/inode.h
struct  inode
{
        char    i_flag;
        char    i_count;        /* reference count */
        int     i_dev;          /* device where inode resides */
        int     i_number;       /* i number, 1-to-1 with device address */
        int     i_mode;
        char    i_nlink;        /* directory entries */
        char    i_uid;          /* owner */
        char    i_gid;          /* group of owner */
        char    i_size0;        /* most significant of size */
        char    *i_size1;       /* least sig */
        int     i_addr[8];      /* device addresses constituting file */
        int     i_lastr;        /* last logical block read (for read-ahead) */
} inode[NINODE];

i_modeの下位12ビットはいわゆるパーミッションで、chmodで使われる4桁の8進数(0755, 0644等)が格納されています。IFDIRのビットが立っていればディレクトリを示します。

i_addrにはディスク上のデータの位置がブロック番号で格納されています。ブロック番号が16bit整数で管理されていることから、サポートされるディスクサイズの上限が 65536 * 512 = 32MB となります。断片化をサポートするため複数のブロックが指定できるようになっています。9ブロック以上使用しているとi_addr[8]に入りきらなくなりますが、そのときの処理はデータブロックの節で説明します。

i_atime, i_mtimeはinode.hの方には含まれていませんが、それぞれ最終アクセス日時・更新日時を示します。1970年1月1日午前0時を起点とする秒数が32bitで格納されています。いわゆるUNIX時間です。intが16bitのため、32bitは2つのintで表現されています。上位・下位はPDP-11特有のミドルエンディアンで表現されています。

ファイルサイズはi_size0(上位), i_size1(下位)で示されます。これは全体で24bitの数値を示しているため、扱えるファイルサイズの上限は16MBとなります。i_size1はcharのポインタ型ですが、ポインタではなく16bit符号なし整数型(uint16_t)として使われています。id:oraccha:20101106によれば当時のC言語(pre K&R)には符号なし整数型がなかったため、ポインタで代用していたとのことです。

ミドルエンディアン

PDP-11は16bitをリトルエンディアンで表現しますが、32bitは上位ワードを先に置くミドルエンディアンと呼ばれる形式を使用しています。具体的には以下の通りです。

エンディアン0x12345678
ビッグ12 34 56 78
リトル78 56 34 12
ミドル34 12 78 56

あくまで想像ですが、PDP-11のCPU上の実装というよりも、ビッグエンディアンの16bitマシンを念頭に書かれたC言語のコードをリトルエンディアンのマシンで動かした結果、ミドルエンディアンが発生したように感じます。

64bit以上はどう表現されるか気になる所ですが、UNIX V6のソースコードで64bitを扱っている箇所はないようです。

データブロック

inode.i_addrでデータブロックの番号が示されます。ブロック番号は1から始まるため、0は「なし」を意味します。連続したブロックでも1つずつ示されます。

使用しているブロックが9個以上でi_addr[8]に収まりきらない場合、imodeにILARGフラグが立ち、i_addrが指すブロックにはブロックマップが来ます。ブロックマップにはデータブロックの番号が1つずつ格納されています。ちなみにILARGのIはinodeの接頭辞で、LARGはlargeの略のようです。

【追記】id:takahirox:20110815:1313398103より。ILARGの場合、i_addr[0〜6]は上記説明の通りですが、i_addr[7]が指すブロックは「ブロックマップのブロックマップ」という二重ポインタとなっています。これによりディスク上限(65536 * 512 = 32MB)をやや上回る(7 * 256 * 512 + 256 * 256 * 512 = 32.875MB)サイズのファイルが理論上マッピング可能になりますが、サイズ自体が24bitのため16MB以上は使用不可となります。

8ブロック以内
  • i_addr → データブロック
9ブロック以上
  • i_addr[0〜6] → ブロックマップ → データブロック
  • i_addr[7] → ブロックマップのブロックマップ → ブロックマップ → データブロック

ディレクトリ

前述のようにinode.i_modeにIFDIRフラグが立っているinodeがディレクトリです。データブロックにはそのディレクトリに含まれるファイルやディレクトリのinode番号と名前が列挙されています。これをディレクトリエントリと呼びます。ファイル名はディレクトリエントリにしか含まれないため、inode単体からファイル名を知ることはできません。

カーネルにはディレクトリエントリの構造体は見当たりません。lsコマンドではユーザー側でディレクトリのデータブロックを読み取ってディレクトリエントリを列挙しています。ファイル名の上限が14文字だということが分かります。

/usr/source/s1/ls.c: readdir()より抜粋
        static struct {
                int     dinode;
                char    dname[14];
        } dentry;

ディレクトリエントリの数はinode.i_nlinkで示されますが、削除されたディレクトリエントリは dinode = 0 の状態でそのまま残っているため、残骸を飛ばしながら列挙する必要があります。

まとめ

イメージからファイルシステムを読み込む手順は以下のようになります。

  1. ルートディレクトリのinodeからデータブロックを取得
  2. データブロックに含まれるinodeを取り出す
  3. inodeがディレクトリなら再帰的に2に戻る

これを実装したのが冒頭のデモです。

2010-07-31

[][][]高速化

id:n7shi:20100727でAlpha逆アセンブラインタプリタ上で動かしましたが、あまりにも遅かったです。使用しているすべてのlibc関数をfopen()等と同じようにF#でインタプリタ側に実装して、ループの無駄等を見直しました。その結果、約10倍ほど高速化しました。

ある種のチートですが、インタプリタ言語ではよくある構造だと思います。Alphaコードの実行はインタプリタのままでJITは行っていません。JITがなくてもこのくらいの速度が確保できれば、簡易Cコンパイラホスティングも視野に入りそうです。

2010-07-27

[][][]逆アセンブラホスティング

C言語でAlphaの逆アセンブラ(以下7d)を開発して、id:n7shi:20100712Silverlight化したAlphaインタプリタ上で動かしてみました。デフォルトでDisassembleのタブに出てくるアセンブリが7dの出力です。横のコンボボックスで従来の組み込み逆アセンブラと切り替えられるようになっています。

ファイルの読み書きはlibcをインタプリタ側でシミュレートしています。C言語からはアドレス決め打ちで呼び出して、インタプリタ側でフックして処理を返しています。

void (*exit)(int) = (void *)0x00ef0000;
int (*fputc)(int, FILE *) = (void *)0x00ef0004;
int (*fgetc)(FILE *) = (void *)0x00ef0008;
FILE *(*fopen)(const char *, const char *) = (void *)0x00ef000c;
int (*fclose)(FILE *) = (void *)0x00ef0010;
int (*fwrite)(const void *, int, int, FILE *) = (void *)0x00ef0014;
int (*fread)(void *, int, int, FILE *) = (void *)0x00ef0018;
int (*fseek)(FILE *, long, int) = (void *)0x00ef001c;