Ext2 directory blocks finden

Heute hab ich wieder große Fortschritte bei der hda4-Rekonstuktion erzielt. Zuerst hab ich nur die Dateien, die find mehr oder weniger geordnet hat einsortiert. Bei der Recherche in der Imagedatei erkannte ich allerdings etwas, auf das ich schon lange hätte kommen können: Ebenso wie die indirect blocks sind auch die Verzeichnisblöcke im Datenbereich. In diesem Eintrag beschreibe ich kurz, wie man verschollene Directoryblöcke bei ext2 anfindet und für was das gut ist...

...und so hab ich erkannt, dass in sehr vielen Fällen, vor allem bei älteren, kleineren Verzeichnissen, das Verzeichnisindex zuerst kommt, gefolgt von den (statistisch korrekt) sortierten Datenblöcken. Mittels dd hab ich das manuell für einige Verzeichnisse gemacht, das hat die Arbeit umgemein erleichert und vor allem kann man sich mehr oder weniger sicher sein, dass die Daten korrekt sortiert sind.

So hab ich jetzt eine gute Redundanz zu meiner vorhandenen Indexdatei in Textform, nebst Dateigrößen in KB-Blöcken.

Aus diesem Grunde hab ich gleich angefangen, ein kleines quick and dirty Programm zu hacken, das mir die Verzeichniseinträge extrahiert. Die einzelnen Verzeichnisse sind zwar nicht zusammenhängend, aber ich nun kann ich die darin enthaltenen Dateien mit meiner Indexdatei vergleichen und so auf das korrekte Verzeichnis schließen.

Wie findet man diese Blöcke? Der große Vorteil ist, dass unter UNIX jedes (korrekte) Verzeichnis zwei “Dateien” hat: ‘.’ und ‘..’, das sind Hardlinks auf das aktuelle und das Vaterverzeichnis.

Der Aufbau eines Eintrages im Verzeichnisblock sieht so aus: 4 Bytes sind das Index für die zugehörge Inode, gefolgt von einem 16-Bit Wert, der die Länge des gesamten Eintrags angibt (die sind aus Performancegründen auf 4 Byte gepadded). Danach zwei 8 Bit Werte, eines der Typ der Datei und das andere die Länge des Dateinamens die folgt. Daraus wird schnell klar, dass jeder Verzeichnisindexblock folgendes Muster aufweisen muss (man berücksichtige das bit alignment)

XX XX XX XX: irgendeine Zahl (inode)
0C 00 : Länge des Records=12 Bytes, also 4+4+padding(strlen("."))
01: Länge des Strings für "."
02: Typ des Elements: Verzeichnis
2E 00 00 00: ASCII Code für "."

Das gleiche wiederholt sich für den ".." Eintrag.

Das Programm scannt das Image also nach Blöcken, die mit diesem Muster anfangen und extrahiert danach alle Verzeichniseinträge.

Ein TODO, das noch fehlt: Das Programm könnte überprüfen, ob zufällig im darauffolgenden Block gleich die Fortsetzung des Datenblocks liegt, sofern ein Block zu klein ist. Die Blöcke müssen zwar nicht zwangsläufig hintereinander sein, jedoch ist die Wahrscheinlichkeit nicht gering.

Vielleicht werde ich das in Zukunft implementieren.

Der erste Prototyp, der gerade das Image scannt, sieht also so aus:

/*
* (c) 2006 Nikolaus Hammler <nobaq@sbox.tugraz.at>
*
* Licensed under GNU GPL!
*/

#define _GNU_SOURCE

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

#include <sys/types.h>
#include <sys/stat.h>
#include <sys/time.h>
#include <sys/ioctl.h>
#include <fcntl.h>
#include <unistd.h>

#define BLOCKSIZE 4096

#define __u32 unsigned long int
#define __u16 unsigned short int
#define __u8 unsigned char

#define _fread(ptr, cnt, len, handle) if(fread(ptr, cnt, len, handle) != cnt*len) \
	{ fprintf(stderr, "warning: read error"); }

// special inodes (include/linux/ext2_fs.h)
#define EXT2_BAD_INO 1 /* Bad blocks inode */
#define EXT2_ROOT_INO 2 /* Root inode */
#define EXT2_ACL_IDX_INO 3 /* ACL inode */
#define EXT2_ACL_DATA_INO 4 /* ACL inode */
#define EXT2_BOOT_LOADER_INO 5 /* Boot loader inode */
#define EXT2_UNDEL_DIR_INO 6 /* Undelete directory inode */

/*
* Ext2 directory file types. Only the low 3 bits are used. The
* other bits are reserved for now.
*/
enum {
	EXT2_FT_UNKNOWN,
	EXT2_FT_REG_FILE,
	EXT2_FT_DIR,
	EXT2_FT_CHRDEV,
	EXT2_FT_BLKDEV,
	EXT2_FT_FIFO,
	EXT2_FT_SOCK,
	EXT2_FT_SYMLINK,
	EXT2_FT_MAX
};

/*
DOCS:
http://www.ussg.iu.edu/hypermail/linux/kernel/0104.1/0096.html

directory entry:

XX XX XX XX | 0C 00 01 02 | 2E 00 00 00 | XX XX XX XX | 0C 00 02 02 | 2E 2E 00 00 |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

*/

char magic1dots[8] = { 0×0C, 0×00, 0×01, 0×02, 0×2E, 0×00, 0×00, 0×00 };
char magic2dots[8] = { 0×0C, 0×00, 0×02, 0×02, 0×2E, 0×2E, 0×00, 0×00 };

inline int isdirent(char *block)
{
	if(!memcmp(block+4, magic1dots, 8) && !memcmp(block+16, magic2dots, 8))
	{
		return 1;
	}

	return 0;
}

int main(int argc, char *argv[])
{
	char block[BLOCKSIZE];
	int blocknr;
	int f;
	FILE *o;

	if(argc <= 1)
	{
		fprintf(stderr, "2 few arguments");
		return 1;
	}

	f = open(argv[1], O_RDONLY | O_LARGEFILE);

	if(!f)
	{
		fprintf(stderr, "could not open file");
		return 2;
	}

	//o = stdout;
	o = fopen("dirlist.txt", "w");
	if(!o)
	{
		fprintf(stderr, "could not open dirlist.txt for writing");
		return 2;
	}

	blocknr = 0;

	while(1)
	{
		unsigned long int ptr = 0;
		//_fread(block, 1, BLOCKSIZE, f);

		if(read(f, block, BLOCKSIZE) != BLOCKSIZE)
		{
			break;
		}

		if(!isdirent(block))
		{
			blocknr++;
			continue;
		}

		// TODO:
		// check for blocks after this one
		while(1)
		{
			ptr = 0;

			fprintf(o, "found directory entry in block %d", blocknr);
			while(ptr <= BLOCKSIZE)
			{
				char fname[256 + 1];
				char typname[1024];

				__u32 inode;
				__u16 rec_len;
				__u8 name_len;
				__u8 file_type;

				inode = *((__u32*)(block+ptr));
				rec_len = *((__u16*)(block+ptr+4));
				name_len = *((__u8*)(block+ptr+6));
				file_type = *((__u8*)(block+ptr+7));

				if(!rec_len)
				{
					fprintf(stderr, "warning: block %d: rec_len=0 –> break", blocknr);
					break;
				}
				if(!inode)
				{
					fprintf(stderr, "warning: block %d: inode=0 –> break", blocknr);
					break;
				}

				if(!name_len)
				{
					fprintf(stderr, "warning: block %d: name_len=0 –> break", blocknr);
					break;
				}

				if(name_len > rec_len)
				{
					fprintf(stderr, "warning: block %d: name_len > rec_len (%d > %d)",
						blocknr, name_len, rec_len);
					break;
				}
				switch(file_type)
				{
					case EXT2_FT_UNKNOWN:
						strcpy(typname, "unknown”);
						break;
					case EXT2_FT_REG_FILE:
						strcpy(typname, "file”);
						break;
					case EXT2_FT_DIR:
						strcpy(typname, "directory”);
						break;
					case EXT2_FT_CHRDEV:
						strcpy(typname, "character device”);
						break;
					case EXT2_FT_BLKDEV:
						strcpy(typname, "block device”);
						break;
					case EXT2_FT_FIFO:
						strcpy(typname, "FIFO”);
						break;
					case EXT2_FT_SOCK:
						strcpy(typname, "socket”);
						break;
					case EXT2_FT_SYMLINK:
						strcpy(typname, "sym-link”);
						break;
					case EXT2_FT_MAX:
						strcpy(typname, "max”);
						break;
					default:
						//fprintf(stderr, \
						// "warning: block %d: invalid file type (0x%02X)", blocknr, file_type);
						strcpy(typname, "”);
						ptr = BLOCKSIZE;
						break;
				}

				if(*typname)
				{
					memset(fname, 0, 256+1);
					memcpy(fname, block+ptr+8, name_len);
					*(fname+name_len) = 0;

					fprintf(o, ” %s [%s], inode: %lu", fname, typname, inode);
	
					fflush(o);
				}

				ptr += rec_len;
			}
			break;
		}
		blocknr++;
	}

	close(f);
	fclose(o);
	return 0;
}