UFS2から削除したテキストファイルを復活する（ASCII/EUC/Shift-JISのみ対応）

ut_undelete.c

/*
UFS2 text undelete
		Lisence: GPL	(C)2004/12/10	nabe@abk

Sorry, Comment is ja_JP.eucJP.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// for mkdir, chdir
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>

// for UFS Filesystem
#include <sys/param.h>
#include <ufs/ufs/dinode.h>
#include <ufs/ufs/dir.h>
#include <ufs/ffs/fs.h>

#define uchar	unsigned char
#define uint	unsigned int
#define uint64	unsigned long long

#define SuperBlock_offset	0x10000
#define FileName_bufsize	0x100000	// 1MB
#define FineName_maxsize	1024		// 1024 chars
#define MaxPathDepth		256		// 最大 dir 数

#define DIR_MODE		0755		// Directory permission

#define ascii_th	100	// 100 byte
#define OUT_DIR		"__out/"
#define OUT_DIR2	"__nofullpath/"
#define INDEX_FILE	"__index.txt"
#define LOSTDIR_fmt	"__inode.%d/"		// %d = inode

#define DIRLIST_FILE	".dir"
#define DIRNAME_FILE	".name"

// ----------------------------------------------------------------------------
struct node_info {
	uint	up_inode;
	uchar	is_dir;		// 0:file 1:directory
	char	*name;
};

// ----------------------------------------------------------------------------
uint	block_size;
uint64	blocks;
uint64	file_size;
uint64	st_block;
uint	ncg;		// number of cg(cylinder group)
uint	inodes;
FILE	*fp;
char	*namebuf;
uint	namebuf_p;
uint	namebuf_size;
char	ascii_tbl[0x200];

uchar	*buf;		// File Reading buffer

struct direct		*dir;
struct ufs2_dinode	*inode;
struct fs		sblock;
struct node_info	*i_info;

//-----------------------------------------------------------------------------
inline int is_directory(char *buf) {
	return (   0x0104000c == *(uint *)(buf+0x04)
		&& 0x0000002e == *(uint *)(buf+0x08)
		&& 0x00002e2e == *(uint *)(buf+0x14) );
}

inline struct direct *next_dir(struct direct *dir) {
	static struct direct *old_dir, *new_dir;
	old_dir = dir;
	new_dir  = (struct direct *)((char *)dir + ((dir->d_namlen + 8 + 4) & 0x1fc));
	if (new_dir->d_ino <= inodes) return new_dir;

	// inode 番号が異常なときは reclen を信用する
	return (struct direct *)((char *)old_dir + old_dir->d_reclen);
}

//-----------------------------------------------------------------------------
// ディレクトリ構造を解析する
//-----------------------------------------------------------------------------
void init_namebuf(uint size) {
	namebuf      = (char *)malloc(size);
	namebuf_p    = 0;
	namebuf_size = size;
}
char *save_name_to_buf(char *s, uint length, uint dir_flag) {
	char *p;
	if (namebuf_p + length + 2 > namebuf_size) {
		fprintf(stderr, "\n\nOverflow of name buffer\nPlease recompile with setting FileName_bufsize\n");
		exit(1);
	}
	p = namebuf + namebuf_p;
	strncpy(p, s, length);
	if (dir_flag) p[length++] = '/';	// directory
	p[length] = 0;	// string terminate
	namebuf_p += length + 1;
	return p;
}

void save_directory_infomation(char *filename) {
	uint i;
	FILE *fp;
	char s[FineName_maxsize];

	for(i=0; i<inodes; i++) i_info[i].name = i_info[i].name - (uint)namebuf;
	sprintf(s, "%s" DIRLIST_FILE, filename);
	fp = fopen(s, "w");
	fwrite(i_info, sizeof(struct node_info), inodes, fp);
	fclose(fp);
	for(i=0; i<inodes; i++) i_info[i].name = i_info[i].name + (uint)namebuf;

	sprintf(s, "%s" DIRNAME_FILE, filename);
	fp = fopen(s, "w");
	fwrite(namebuf, 1, FileName_bufsize, fp);
	fclose(fp);
}
// 0:false 1:true
int load_directory_infomation(char *filename) {
	uint i;
	FILE *fp;
	char s[FineName_maxsize];

	sprintf(s, "%s" DIRLIST_FILE, filename);
	fp = fopen(s, "r");
	if (!fp) return 0;
	fread(i_info, sizeof(struct node_info), inodes, fp);
	fclose(fp);
	for(i=0; i<inodes; i++) i_info[i].name = i_info[i].name + (uint)namebuf;

	sprintf(s, "%s" DIRNAME_FILE, filename);
	fp = fopen(s, "r");
	fread(namebuf, 1, FileName_bufsize, fp);
	if (!fp) return 0;
	fclose(fp);

	return 1;
}


void analyze_directory(FILE *fp) {
	uint64 i;
	uint k,x;

	// st_block = 282272;
	for(i=st_block; i<blocks; i++) {
		if (!((uint)i & 0x3f)) printf("Directocy analyze : %lld / %lld\r", i, blocks);
		fseek(fp, i*block_size, SEEK_SET);
		fread(buf, 1, block_size, fp);
		// if (i>280000) printf("\n");

		// found directory
		if (is_directory(buf)) {
			// "." dir
			dir = (struct direct *) buf;
			k   = dir->d_ino;
			dir = next_dir(dir);

			// ".." dir
			i_info[k].up_inode = dir->d_ino;
			dir = next_dir(dir);

			while(dir->d_ino) {
				x = dir->d_ino;		// inode number
				i_info[x].up_inode = k;	// 親
				if (dir->d_type == DT_DIR) i_info[x].is_dir = 1;
				// 名前の設定
				i_info[x].name = save_name_to_buf(dir->d_name, dir->d_namlen, i_info[x].is_dir);
				dir = next_dir(dir);
			}
		}
	}
	printf("Directocy analyzed                    \n");
	/*
	for(i=2; i<inodes; i++)
		if (i_info[i].up_inode) printf("[%3lld] = up to %3d\n", i, i_info[i].up_inode);
	*/
}

inline void get_pathname(char *fnbuf, uint inode) {
	static uint nstack[MaxPathDepth];
	uint p;
	char *s,s2[16];

	if (inode==2) {		// is Root
		*fnbuf = 0; return;
	}
	p = 0;
	while(inode) {
		if (i_info[inode].is_dir) nstack[p++] = inode;
		inode = i_info[inode].up_inode;
		if (inode == 2) break;	// is Root
		if(p >= MaxPathDepth) {
			printf("direoctory chain looped?\n");
			sprintf(fnbuf, OUT_DIR2 LOSTDIR_fmt, nstack[0]);
			mkdir(fnbuf, DIR_MODE);	// directory 作成
			return;
		}
	}
	if (!inode) {
		fnbuf = strcpy(fnbuf, OUT_DIR2);
	} else	*fnbuf = 0;
	// directory 連結
	while(p) {
		s = i_info[nstack[--p]].name;
		if (!s) {
			sprintf(s2, LOSTDIR_fmt, nstack[--p]);
			s = s2;
		}
		fnbuf = strcat(fnbuf, s);
		mkdir(fnbuf, DIR_MODE);	// directory 作成
	}
}

//-----------------------------------------------------------------------------
// テキスト判別用テーブルの作成
//-----------------------------------------------------------------------------
void init_ascii_tbl() {
	int i;

	// 第 1byte
	for (i=0; i<=0xff; i++) ascii_tbl[i] = 0;
	// ASCII
	ascii_tbl['\t'] = 1;
	ascii_tbl[0x0A] = 1;
	ascii_tbl[0x0d] = 1;
	ascii_tbl[0x0e] = 1;	/* JIS shift IN */
	ascii_tbl[0x0f] = 1;	/* JIS shift OUT */
	ascii_tbl[0x1b] = 1;	/* ESC sequence */
	for (i=0x20; i<0x80; i++) ascii_tbl[i] = 1;

	/* Shift-JIS or EUC */
	for (i=0x81; i<0xa0; i++) ascii_tbl[i] = 2;
	/* 半角カタカナ or EUC */
	for (i=0xa0; i<0xe0; i++) ascii_tbl[i] = 1;
	/* Shift-JIS or EUC */
	for (i=0xe0; i<0x100;i++) ascii_tbl[i] = 2;

	// 2byte
	for (i=0x100; i<=0x1ff;i++) ascii_tbl[i] = 0;
	/* Shift-JIS 第 2byte */
	for (i=0x140; i<=0x17e;i++) ascii_tbl[i] = 1;
	for (i=0x180; i<=0x1fc;i++) ascii_tbl[i] = 1;
	/* EUC 第 2byte */
	for (i=0x1a1; i<=0x1fe;i++) ascii_tbl[i] = 1;
}
// ----------------------------------------------------------------------------

int main(int argc, char *argv[]) {
	uint64 i, txt_stblock;
	uint j;
	uint x;
	FILE *save_fp, *index_fp;
	char *p;
	char imgfile[FineName_maxsize];
	char str[FineName_maxsize], outdir[FineName_maxsize];
	save_fp = index_fp = NULL;

	//////////////////////////////////////////////////////////////
	// 引数解析
	//////////////////////////////////////////////////////////////
	if (argc < 2) {
		printf("Usage: %s UFS2-dump-image-file\n", argv[0]); return 1;
	}

	// 文字テーブル初期化
	init_ascii_tbl();

	// ファイルオープン
	 p = argv[1];
	fp = fopen(p, "r");
	if (!fp) {
		fprintf(stderr, "file open error!!\n"); exit(1);
	}
	// ファイル名のみ取り出す
	x=j=0;
	while(p[j]) {
		if (p[j++]=='/') x = j;
	}
	strncpy(imgfile, &p[x], FineName_maxsize);	// without path

	//////////////////////////////////////////////////////////////
	// スーパーブロックを読み出す
	//////////////////////////////////////////////////////////////
	fseek(fp, SuperBlock_offset, SEEK_SET);		// offset 0x10000
	fread(&sblock, 1, sizeof(sblock), fp);

	block_size = sblock.fs_fsize;		// ブロックサイズ
	blocks     = sblock.fs_size;		// ブロック数
	file_size  = block_size * blocks;
	st_block   = sblock.fs_dblkno;		// 最初のデータ blockオフセット
	ncg        = sblock.fs_ncg;		// シリンダグループ数
	inodes     = sblock.fs_ipg * ncg;	// 全 inode 数

	// ファイル読み込みバッファ確保
	buf = calloc(block_size * 4, 1);	// 余分に確保
	buf[block_size] = 0xa1;			// for TEXT check

	// 表示
	printf("Image file  : %s\n", str);
	printf("file size   : %lld\n", file_size);
	printf("block size  : %d\n", block_size);
	printf("blocks      : %lld\n", blocks);
	printf("start block : %lld\n", st_block);
	printf("n of cg     : %d\n", ncg);
	printf("n of inode  : %d\n", inodes);

	//////////////////////////////////////////////////////////////
	// (1pass) ディレクトリ構造の解析
	//////////////////////////////////////////////////////////////
	init_namebuf(FileName_bufsize);
	i_info = (struct node_info *)calloc(inodes, sizeof(struct node_info));

	if (!load_directory_infomation(imgfile) ) {
		analyze_directory(fp);
		save_directory_infomation(imgfile);
	}

	//////////////////////////////////////////////////////////////
	// directory 作成
	//////////////////////////////////////////////////////////////
	mkdir(OUT_DIR, DIR_MODE);
	chdir(OUT_DIR);		// 作業ディレクトリ

	mkdir(OUT_DIR2, DIR_MODE);

	//////////////////////////////////////////////////////////////
	// (2pass) ファイル解析
	//////////////////////////////////////////////////////////////
	txt_stblock = 0;
	strcpy(outdir, OUT_DIR2);	// 出力 dir
	for(i=st_block; i<blocks; i++) {
		if (!((uint)i & 0x3f)) printf("%lld / %lld\r", i, blocks);
		fseek(fp, i*block_size, SEEK_SET);
		fread(buf, 1, block_size, fp);

		// found directory
		if (is_directory(buf)) {
			dir = (struct direct *) buf;
			get_pathname(outdir, dir->d_ino);

			// index file open
			sprintf(str, "%s" INDEX_FILE, outdir);
			if (index_fp) fclose(index_fp);
			index_fp = fopen(str, "w");
			if (!index_fp) {
				printf("file open error : %s\n", str); exit(1);
			}
			printf("[%lld] found directory %s\n", i, outdir);
			fprintf(index_fp,"block number=%lld, Directory=%s\n\n", i, outdir);

			dir = next_dir(dir);	// "."  を skip
			dir = next_dir(dir);	// ".." を skip
			while(dir->d_ino) {
				x = dir->d_namlen;	// 名前の長さ
				*str = 0;
				strncpy(str, dir->d_name, x);
				str[x] = 0;
				printf("inode=%d, type=%x, name=%s\n", dir->d_ino, dir->d_type, str);
				if (dir->d_type != DT_DIR)
					fprintf(index_fp, "inode=%d, file name=%s\n" , dir->d_ino, str);
				else	fprintf(index_fp, "inode=%d, directory=%s/\n", dir->d_ino, str);
				dir = next_dir(dir);
			}
			j = 0;	// 必須
		} else {
			// ascii counter
			j=0;
			j+=ascii_tbl[buf[j]];
			j+=ascii_tbl[buf[j]];
			j+=ascii_tbl[buf[j]];
			for (   ; j<block_size; ) {
				if (! ascii_tbl[buf[j]]) break;
				if (  ascii_tbl[buf[j]]==1) {
					j++; continue;	// Ascii
				}
				if (! ascii_tbl[buf[j] + 0x100]) break;
				j++;
			}
		}

		// テキストファイルと見なす
		if (txt_stblock || j>=ascii_th) {
			if (!txt_stblock) {
				sprintf(str, "%s%06lld.txt", outdir, i);
				save_fp  = fopen(str, "w");
				if (!save_fp) {
					printf("file open error : %s\n", str); exit(1);
				}
				txt_stblock = i;
			}
			if (j > block_size) j = block_size;
			
			fwrite(buf, 1, j, save_fp);	// j byte write
			
			if (j < block_size) {
				printf("[%lld] wrote %s%06lld.txt, %lld byte\n", txt_stblock, outdir, i,(i-txt_stblock)*block_size + j);
				fclose(save_fp);
				txt_stblock = 0;
			}
		}
	}

	if (index_fp) fclose(index_fp);
	fclose(fp);

	return 0;
}

ut_undelete.txt

///////////////////////////////////////////////////////////////////////////////
UFS2 text undelete
			(C)2004/12/10 nabe@abk
			License : GPL
///////////////////////////////////////////////////////////////////////////////

■概要

　"rm -rf *" してしまったファイルを復活させるため、諸事情により作成したテキ
ストファイル専用のファイル復活ツールです。専門的なツールであるため、あまり
知識のない方は使用しないでください（危険はありませんが……）。使用する場合
もこのテキストをよく読んでからにしてください。

　動作確認は FreeBSD 5.3 にて行いましたが、UFS2 ファイルシステムであれば、
おそらく問題なく使用出来ます。テキストファイルは、Shift-JIS、EUC-JP、JIS に
対応しています。テキストファイル以外は復活できません。


■原理と制約

・ファイルシステムの解釈は、カーネルソースから適当に行いました。
　もし仕様書の在処を知っている方が居ましたら、教えてください。

・FreeBSD Kernel はファイル削除時、inode に削除というフラグを立てるのではなく、
　inode のほぼすべての情報を消去します。よってファイルの情報（所有者、サイズ、
　ディスク上での実体データの繋がり）は完全に消えており、FAT のような undelete 
　は原理上不可能です。

・このツールでは、一つのファイルはディスク上の連続した領域を使用すると仮定し、
　すべてのクラスタをスキャンしています。そして、あるサイズ（100byte に設定）を
　越えた連続したテキストデータをファイルとして出力します。

・上記の機能を持ったファイル復元ツールは沢山ありますが、このツール独自の機能
　としてディレクトリ構造を解析しています。ディレクトリエントリの直後に、その
　ディレクトリ内のファイルが存在するという仮定の元、ディレクトリ構造の復元を
　試みます（あまりアテにはなりませんが、無いよりはマシなようです）。


■使い方

　UFS2 のイメージファイルが必要です。デバイスの「ディスクラベル」を丸ごと
ダンプしてください（mount できる単位を dump してください）。こちらでは、

	$ cat /dev/ad0s1d >imgfile.bin

　などとしました（言うまでもないことですが、復活させたい領域にイメージファ
イル出力しませんように）。
　本ツールを

	$ gcc -O2 -o ut_undelete ut_undelete.c

　としてコンパイルした後、空き容量が十分にあるディレクトリで、

	$ ./ut_undelte /[path]/imgfile.bin

　としてください。"__out" 以下に復元したファイルが現れます。ディレクトリ構
造の復元を試みますが、どこのディレクトリに所属するか推測出来なかったファイ
ルについては "__out/__nofullpath/" 内に展開されます。

	imgfile.bin.dir
	imgfile.bin.name

　の二つのファイルはディレクトリ構造の解析結果を格納したキャッシュです。必
要ないので消してください（パラメーターを変更し何度も実行する場合や、プログ
ラムを改造しながらテストする場合は使用すると便利です）。


■詳しい原理

　テキストファイル判別は説明することがないぐらい単純ですので、ディレクトリ
構造の解析について簡単に説明しておきます。

$ ls -ial
117764 drwxr-xr-x  4 root  wheel   512 12  2 16:18 ./
117763 drwxr-xr-x  3 root  wheel   512 11 27 01:34 ../
117768 -rw-r--r--  1 root  wheel   423 11  5 10:27 PROTO.localhost-v6.rev
117767 -rw-r--r--  1 root  wheel   423 11  5 10:27 PROTO.localhost.rev
117771 -rw-r--r--  1 root  wheel  1093 11  5 10:27 make-localhost
117765 drwxr-xr-x  2 root  wheel   512 12  2 16:18 master/
117769 -rw-r--r--  1 root  wheel  3839 12  2 16:18 named.conf
117791 -rw-r--r--  1 root  wheel  3754  8 26 22:40 named.conf.old
117770 -rw-r--r--  1 root  wheel  2600 11  5 10:27 named.root
117766 drwxr-xr-x  2 bind  wheel   512 12  2 16:17 slave/

　という感じで一番左に表示される値が、右のファイルの実体である inode 番号を
示しています。ディレクトリエントリには、この inode 番号と名前のみが記録され
ていて（struct direct）、本来はその inode から得られるディスクブロック番号
のリストを辿ることでファイル内容を得ることができます。
　このディレクトリ情報自体は普通のファイルとして、データ領域に存在します。
inode ではないので消去されません。"." のエントリと ".." のエントリが必ず存
在することを利用して、ディレクトリファイルを判別しています。エントリは可変
長のデータの連なりとなっています。ファイルを削除したりすると、そのエントリ
を読み飛ばすように一つ前のエントリのレコード長が長くなったりします。これで
はディレクトリ内のファイルエントリ発見が困難であるため、一つ一つファイル名
の長さから区切りを見つけています。

　さて、master というディレクトリ以下にどんなファイルが存在するか知りたい
とき、通常ならば inode の 117765 みればよいのですが、この情報は抹消されて
います。しかし、もし master というディレクトリファイルが残っていれば、

$ ls -ial master/
117765 drwxr-xr-x  2 root  wheel  512 12  2 16:18 ./
117764 drwxr-xr-x  4 root  wheel  512 12  2 16:18 ../
117798 -rw-r--r--  1 root  wheel  409 12  2 16:17 any.dom
117799 -rw-r--r--  1 root  wheel  425 12  2 16:19 localhost-v6.rev
117800 -rw-r--r--  1 root  wheel  425 12  2 16:19 localhost.rev

　という情報が得られ、ここから inode 番号を比較することによって、このディ
レクトリは master ディレクトリ内に位置することが判明します。全クラスタに対
してこの処理を繰り返すことで、可能な限りディレクトリ情報の復元を試みます。
　また、ルートの inode は常に 2 番であることも利用しています。

　このルーチンはかなりうまく動作しています。しかしながら、ディレクトリエン
トリの後に実際のファイルがあるという仮定がなかなか満たされないらしく、あま
りアテになりません。
　例えば、tar.gz のようなファイルを展開したり、どこからかファイルをコピーし
た直後に消去したならばまだしも、使い込んだディスクほどこの仮定が満たされる
ことは少ないでしょう。ですから、おまけ程度の機能と思ってください。


■テキストファイル以外への対応

・テキストファイル以外への対応は、ファイルヘッダの解析ルーチンを増やせば
　いくらでも可能です。そんなに難しくはないのでぜひ挑戦して、再配布するな
　り送りつけるなりしてください。

　ソースは C で平易に書いたつもりです。そんなに難しく書いてはいないと思
いますが、疑問点があれば掲示板なりで質問してください。（ディレクトリ構造
解析は多少難しいかも知れませんが）。


■制約

・ファイルシステムは UFS2 決め打ちです。
・ディレクトリ情報がディスクのブロックサイズ（フラグメーテーションサイズ）
　を越えた場合、その先は無視されます（対応は容易ですが必要なかったので）。

以下４つの制約は、ソースの定義文を変更することで可能です。

・スーパーブロックは領域先頭から 64KB にあると仮定しています。
・すべてのファイルの名前を全てトータルした長さは 1MB までです。
・一つのファイル名は 1024 byte までです（パス含む）。
・ディレクトリの階層は 256 階層までです。

■一言

　inode をあそこまで綺麗に消すことないじゃん……（涙）