演習2の解答例 2006年12月22日 海谷 治彦.

Slides:



Advertisements
Similar presentations
プログラミング演習Ⅱ 課題 4 第 2 週 画像ファイル (ppm) の読み書き 画像データ用のメモリ確保・解放 1.
Advertisements

プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
システムプログラミング 第7回、8回 ファイルシステム関連の システムコール
■パス検索 各種ファイルを操作するには、まずパス名をiノードに変換しなければならない。 以下にパス名をiノードに変換する関数の説明を行う。
情報処理演習C2 ファイル操作について (2).
情報基礎演習B 後半第5回 担当 岩村 TA 谷本君.
数理情報工学演習第一C プログラミング演習 (第3回 ) 2014/04/21
ファイルシステムの構造 外部記憶装置のパーティション(区画) ファイルシステムとパーティション(区画) ファイルシステムのmount
データ構造とアルゴリズム 第10回 mallocとfree
画像ファイル(ppm)の読み書き 画像データ用のメモリ確保・解放
基礎プログラミングおよび演習 第9回
プログラミング演習Ⅱ 第12回 文字列とポインタ(1)
プログラミング演習II 2004年12月 21日(第8回) 理学部数学科・木村巌.
プログラミング論 II 電卓,逆ポーランド記法電卓
第7章 データベース管理システム 7.1 データベース管理システムの概要 7.2 データベースの格納方式 7.3 問合せ処理.
プログラミング演習Ⅰ 課題2 10進数と2進数 2回目.
Linuxカーネルについて 2014/01.
オペレーティングシステム i386アーキテクチャ(2)
画像ファイル(ppm)の読み書き 画像データ用のメモリ確保・解放
データ構造と アルゴリズム 第四回 知能情報学部 新田直也.
構造体 構造体, 構造体とポインタの組み合わせ,.
二分探索木によるサーチ.
岩村雅一 知能情報工学演習I 第8回(後半第2回) 岩村雅一
Cプログラミング演習 中間まとめ2.
データ構造とアルゴリズム 第4回 リスト ~ データ構造(1)~.
プログラミング 4 記憶の割り付け.
プログラミング演習I 2003年6月25日(第10回) 木村巌.
アルゴリズムとデータ構造 補足資料11-1 「mallocとfree」
プログラミング演習I 2003年5月7日(第4回) 木村巌.
演習1の解答例の解説 2004年10月21日 海谷 治彦.
プログラミング演習Ⅱ 課題4第3週 画像処理 (1) ビット演算子.
第7回 プログラミングⅡ 第7回
アルゴリズムとデータ構造 補足資料4-1 「メモリと配列」
アルゴリズムとデータ構造 補足資料5-1 「メモリとポインタ」
地域情報学 C言語プログラミング 第5回 ポインタ、関数、ファイル入出力 2017年11月17日
演習1の解答例の解説 2006年11月8日 海谷 治彦.
P n ポインタの基礎 5 q m 5 7 int* p; int 型の変数を指すポインタ int* q; int 型の変数を指すポインタ int n=5, m=7; int 型の変数 int array[3]; int* pArray[3]; p = &n; ポインタにアドレスを代入しているのでOK.
TCP/IPとプロセス間通信 2007年1月12日 海谷 治彦.
先進的計算基盤システムシンポジウム SACSIS2007併設企画 マルチコアプログラミングコンテスト 「Cellスピードチャレンジ2007」
情報処理 タイマの基礎 R8C タイマの基礎.
システムプログラミング 第7回、8回 ファイルシステム関連の システムコール
情報処理Ⅱ 第2回:2003年10月14日(火).
オペレーティングシステム2006 ファイル管理 (3) 演習へのヒント他
配列変数とポインタ 静的確保と動的確保 ポインタ配列 2次元配列 時間計測 第1回レポートの課題
プログラミング演習I 2004年5月19日(第5回) 理学部数学科・木村巌.
システムプログラミング 第7回、8回 ファイルシステム関連の システムコール
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
プログラミング言語論 第六回 理工学部 情報システム工学科 新田直也.
データ構造とアルゴリズム 第11回 リスト構造(1)
文字列へのポインタの配列 static char *lines[MAXLINES]; lines[0] NULL
プログラミング演習I 2003年7月2日(第11回) 木村巌.
vc-3. ダンプリスト,配列 (Visual Studio C++ の実用知識を学ぶシリーズ)
ファイルの読み込み, ファイルからのデータの取り出し, ファイルの書き出し
第11回放送授業.
アルゴリズムとデータ構造1 2009年6月15日
R8C I/Oポートの仕組み SFR定義ファイルの中身.
ネットワーク・プログラミング Cプログラミングの基礎.
vc-3. ダンプリスト,配列 (Visual Studio C++ の実用知識を学ぶシリーズ)
情報処理Ⅱ 2006年11月24日(金).
ドキュメントジェネレータ 詳細仕様 長谷川啓
アルゴリズムとデータ構造 2010年6月17日
全体の流れ 画像ファイルを開き,画像データをメモリ上にロード メモリ上にロードした画像データに処理を加える
データ構造と アルゴリズム 第四回 知能情報学部 新田直也.
プログラミング演習II 2004年11月 16日(第5回) 理学部数学科・木村巌.
ネットワーク・プログラミング プロセスとファイルシステム管理.
プログラミング演習II 2003年12月10日(第7回) 木村巌.
マスク合成(のような処理) 出力画像 Out 入力画像1 In1 In1 In2 Out 入力画像2 In
左右反転と180度回転 [0][xsize – 1] [0][0] → i ↓ j [ysize – 1][xsize – 1]
TList リスト構造とは? 複数のデータを扱うために、 データの内容と、次のデータへのポインタを持つ構造体を使う。
プログラミング演習II 2003年10月29日(第2,3回) 木村巌.
Presentation transcript:

演習2の解答例 2006年12月22日 海谷 治彦

目次 演習2編 機種依存の話 Ext2の構造,ext2_dir_entry_2 ディレクトリエントリの終端は? 解答例1 ブロック毎にちまちま読んでいく 解答例2 1.5MBくらいのデータ,いっきに読み! 機種依存の話 バイトオーダー問題 Padding問題

演習で使うFSの構造 (ブロックグループが1個) 1440個のブロック, ブロックサイズは1024B 全部で 1474560 B iノードを184個分 (8×23) 1個 23個 1412個 1 2-2 3 4 5-27 28-1439 ブート ブロック スーパー ブロック グループ ディスクリプタ データ ブロック ビットマップ iノード ビットマップ iノード テーブル データ ブロック 41 カーネル本 p.577 1ブロック 1ブロック 複数ブロック 1ブロック 1ブロック 複数ブロック 複数ブロック ココはExt2で使わない 演習3ではココ(0から数えて41個目)を使う

演習2の大まかな流れ ブロック41を取り出す. その中身を構造体 ext2_dir_entry_2 に従い解析する. サンプル getblock.c (任意のブロックを切り出すもの) その中身を構造体 ext2_dir_entry_2 に従い解析する. この構造体は可変長なのでタチが悪い. 個々のインスタンスの長さは読み込んで,メンバーrec_lenの値を読まないと解らない. よって,まずは本構造体が最大長であると仮定して,ext2_dir_entry_2 構造体に読み込み,rec_len の長さを得て,次のインスタンスまでポインタを進めればよい. 上記がヒントですが,さらに多少の工夫が必要.

ext2_dir_entry_2 型: 1 通常ファイル, 2 ディレクトリ, 7 シンボリックリンク 他 // include/linux/ext2_fs.h の501行目 struct ext2_dir_entry_2 { __u32 inode; // そのディレクトリのiノード番号 __u16 rec_len; // 構造体のサイズ,name[]のため可変 __u8 name_len; // ファイル名の長さ \0 は含まず __u8 file_type; // ファイルの型番号 char name[EXT2_NAME_LEN]; // ファイル名 }; 通常,255 効率化のため4の倍数長になっている.不要な部分には \0 文字が詰めてあるはずなんだが・・

例: とあるデータブロックの中身 file_type inode番号 rec_len name 21 12 1 2 . \0 \0 \0 22 12 2 2 . . \0 \0 53 16 5 2 h o m e 1 \0 \0 \0 67 28 3 2 u s r \0 16 7 1 o l d f i l e \0 34 12 4 2 s b i n name_len

ディレクトリ・ブロックの終端は? inodeにも,ディレクトリデータが入ったブロックにも,ディレクトリ数のデータは入っていない. じゃ,どうやってディレクトリのリストの末尾をみつけるかというと・・・・ 次のページ参照. 結果として,各エントリのサイズの合計がブロックサイズに一致した時が末尾ということになる.

例: とあるデータブロックの中身 file_type inode番号 rec_len name 21 12 1 2 . \0 \0 \0 22 12 2 2 . . \0 \0 53 16 5 2 h o m e 1 \0 \0 \0 67 28 3 2 u s r \0 16 7 1 o l d f i l e \0 34 940 4 2 s b i n \0 \0 全部足して,ブロックサイズ(1024B)になるように最後のエントリのサイズが設定されている. 結果として,末尾に詰め物(Padding)がされている.

演習でのブロックの場合 足して 1024B inode = 12, (.) (lec_len = 12) inode = 21, (exercise1) (lec_len = 20) inode = 22, (os1.pdf) (lec_len = 16) inode = 23, (index.html) (lec_len = 20) inode = 24, (chroot.txt) (lec_len = 20) inode = 17, (image) (lec_len = 924) 足して 1024B

バイトオーダー問題 前述のようにBigEndianマシンの場合,提供したイメージがLittleEndianを想定しているので,バイトオーダー変換をしないといけない. オーダー(順序)がひっくり返るのは,int とか short とかの単純データ型内のみです. 構造体の中全体がひっくり返っているわけではない. ま,自分でオーダーをひっくり返してもいいけど,こちらからひっくり返すマクロを提供した.

rev16 #define rev16(x) (((x&0x00ff)<<8) | ((x&0xff00)>>8)) 元データx (16bit = 2byteを想定) x & 0x00ff は以下 x & 0xff00 は以下 00 00 <<8 は8bit左シフト >>8 は8bit右シフト 00 | は論理(というかbit)和 | ⇒ 00

解答例1 (ex3.c) 基本的にはサンプルプログラムをベースにブロック単位にデータを読む方法ととる. unsigned char* get_dir_entry( struct ext2_dir_entry_2* de, unsigned char* block, int* resta ) blockで指定されたアドレスからext2_dir_extry_2構造体を切り出して,結果を *deに入れる. blockのデータがあと何Bのこっているかのカウンタを *resta に保持. 返り値は次に構造体を読み出すべきアドレスの先頭.読みきった場合,NULLが返る. de->nameに対しては終端文字を埋め込む.(実はちょっと危険)

解答例2 (ex3b.c) このファイルシステムは所詮,たった1.5Mしかないので,ちまちまブロック単位に読まず,一気に全データを配列 blocksに読み込むプログラム. ま,lseek()を使うというのもアリなんですが・・・・ 実は演習4ではこのスタイルのほうが断然便利. // 1024*1440 = 1474560 #define ALLBLOCKSIZE 1474560 #define BLOCKSIZE 1024 #define BLOCKNUMBER 1440 // ココに全部よみこんじゃう unsigned char blocks[ALLBLOCKSIZE]; unsigned char* nth_block(int n){ // ブロック先頭を得る関数 if(n<0 || BLOCKNUMBER<=n) return NULL; // out of range return blocks+(n*BLOCKSIZE); }

機種依存問題について

バイトオーダー 2バイト以上のデータを保存したり通信転送したりする場合,最上位のデータから送る場合と,最下位から送るかの違いがCPUによってある. 最上位: Big Endian と呼ぶ PPC (Power PC, Macに搭載)のCPUはこっち 最下位: Little Endian と呼ぶ i386 (WinPC)のCPUはこっち i386の場合は順序がひっくり返っている!

境界整列問題 データの境界が必ず2バイト単位になるように内部的に調整しているようなマシンがある.(e.g. mc68000等) その場合,この演習でやった bcopy()やmemcpy()を使った戦略は破綻する.

例 メモリ上の配列配置 struct funny{ char flag; long int value; }; に対して, }; に対して, 1 1 Padding (詰め物)と呼ぶ 3 4 3 4 5 6 5 6 7 8 7 8 別のマシン(MPU) たとえば8086 とあるマシン(MPU) たとえばMC6800