File system type and data recovery chances

File systems regulate the way of allocating, storing and manipulating the data on a data storage medium. As the file system is mainly responsible for the data management, it certainly defines the method of handling data during and after its deletion. Thus, the chances for complete and successful data recovery depend drastically on the file system behavior.

Virus attacks and logical failures make system behavior unpredictable: whether the system will follow its strict algorithms for ordinary user mistakes in form of files deletion or file system formatting. For this reason, we address two cases of data loss here– file deletion and system formatting (with the same file system).

Let us have a closer look at Windows file systems, such as NTFS, FAT/FAT32 or ExFAT; Mac OS X HFS+ file system or Linux file systems, such as Ext2, Ext3/Ext4, ReiserFS, XFS or JFS.

Windows file systems

NTFS file system
Specifics

Structure: file system header (boot record), Master File Table ($MFT), place for files:


NTFS structure

The NTFS file system uses Master File Table (MFT) for files coordination. Basically, MFT contains information about all files and folders holding these files. This information, to be specific, includes file location, name, size, date and time of its creation and last modification.

If the file attributes are too big for one MFT cell to hold it, the file system will allocate another cell placed in a file for file attributes list.


File deletion

Procedure: the file system does not delete and rather labels a file record in the MFT as unused and marks file location in the MFT and Bitmap as released. The system also deletes file entry from its directory.

Recovery: the information about the deleted file (name, size, location) remains in the MFT. If the MFT record remains unchanged and the disk data are not overwritten, file recovery chances are 100%. Yet, if this record is deleted, it is still possible to find the file by its content with help of a raw-recovery method (recovery by disk contents and bypassing file system structure).


Formatting

Procedure: the file system wipes the beginning of the MFT only. The MFT tail remains unchanged.

Recovery: the first 256 files lose their links to MFT, thus their recovery is only possible with the raw-recovery method. Recovery chances for the files following these 256 files is up to 100%.




FAT/FAT32 file system
Specifics

Structure: file system header (2 headers more for FAT32), FAT tables, and the data area.


FAT/FAT32 structure

The FAT file system applies the File Allocation Table containing an entry for each cluster on the disk and making a link from this table to a file location on the disk. It also holds links to a cluster of the file start, file continuation and file end. The FAT file system does not apply defragmentation of fragmented files. As to its original design, the files on FAT have 8 symbols for file name and 3 symbols for file extension. That is why the file system stores long file names separately utilizing long file names (LFN) extension feature.


File deletion/Formatting

Procedure: the file system deletes all the information contained in the File Allocation Table including the links to a file continuation and an end cluster. The data area itself is not wiped, though. The first symbol of a file name is deleted in its short form, and with FAT 32, deleted is the part of information about the start file cluster.

Recovery: the file start can be found, as the information about the file continuation and the end needs assumption. For this reason, data recovery may be incomplete. Besides, the FAT file system doesn’t defragment files making it difficult to retrieve fragmented files even with the raw recovery method. Another issue is file names limited in length and can even be stored in a detached disk place. Recovery of long file names may give no effect.




ExFAT file system
Specifics

Structure: file system header, a FAT table, and the data area.


ExFAT structure

Like its predecessors, the ExFAT file system applies the File Allocation Table to manage files. This table contains an entry for each cluster on the disk and makes a link from this table to a file location on the disk. It also holds links to the file start, file continuation and file end. This file system tries to avoid file fragmentation. The file system does not provide linking to file sub-directories.


File deletion/Formatting

Procedure: the file system deletes all the information contained in the File Allocation Table including the links to file continuation and end. The data area itself is not wiped, though.

Recovery: as links to files continuation may be lost, the recovery result for files with a size of several blocks can be incomplete. The chances for successful recovery of a file in case of a directory damage can be low as well. At the same time, recovery of files by their contents (raw recovery method) may give highly positive results due to low files fragmentation.




Mac OS file systems

HFS+ file system
Specifics

Structure: file system header; file system journal; a Ctalog File with the files containing information about other files (so called hard-link files).


HFS+ structure

The HFS+ file system supports journaling. File system journal keeps track of all file system modifications. The HFS+ journal is limited in its size, the new information being added and written every time over old journal records. In this way, the file system overwrites older information to release the journal for data about newer file system modifications.

The HFS+ file system aims at files defragmentation. The file system thoroughly looks for a place to store a file, and literary glues file fragments together in the found one. Still, remaining fragmented files can impose a problem to recovery result.

HFS+ supports hard links stored as separate files inside a hidden HFS+ root directory and serving to store information about a user file. Each hard-link file is bound to its user file.


File deletion

Procedure: the file system deletes a hard link from the directory. Nevertheless, it still keeps this information in its journal records for some time.

Recovery: the program can address the file system journal to find an older file system state and return the lost hard link in its place. Data recovery chances will depend greatly on the time the system is used after the file deletion. Yet, if the journal record has been emptied, you can try raw recovery, which can give excellent results for non-fragmented files.


Formatting

Procedure: the file system deletes the hard-link directory leaving the journal and on-disk data area intact.

Recovery: the program addresses the file system journal to recover everything that is recoverable from the journal or employ raw recovery (by file contents) to retrieve lost files. Recovery chances may be low for fragmented files due to hard-links deletion.




Linux file systems

Ext2 file system
Specifics

Structure: file system header; inode; inode table.


Ext2 structure

The Ext2 file system uses inodes containing information about files. This information includes user and group ownership, access mode and extension. Some inodes include an inode table copy.

The inodes do not include file contents and file names, as they are stored in file directories and are not considered to be metadata according to the file system.


File deletion

Procedure: Ext2 labels the file inode as free and updates the map of free blocks. The file name entry is unlinked from the directory record. File name to node reference is wiped. The file will be deleted as soon as all inode references to this file are deleted.

Recovery: due to file descriptions remaining in the inode, the chances to retrieve the file are quite high. Nevertheless, file names stored in directories and unlinked from the file, will be lost.


Formatting

Procedure: Ext 2 wipes all file allocation groups and deletes file inodes.

Recovery: the program can apply raw-recovery method to find files by their contents. Recovery chances depend on file fragmentation: fragmented files are hard to retrieve.




Ext3/Ext4 file system
Specifics

Structure: file system header; inode; inode table.


Ext3 and Ext4 structure

In addition to inodes implemented in Ext2, Ext3 and Ext4 file systems use file system journaling. The file system journal keeps track of all modifications made by the file system. Ext4 differs from the Ext3 file system by the references structure.


File deletion

Procedure: The file system makes entry to the journal and then wipes the file inode entry. The directory record is not deleted completely and rather the order for directory reading is changed.

Recovery: retrieval of deleted files even with the file name is possible due to file system journal. Still, the recovery result depends on the time the file system remains in operation after file deletion.


Formatting

Procedure: All allocation groups as well as file nodes and even the journal are wiped. File system journal may still contain information about some of the recently created files.

Recovery: retrieval of lost files is only possible with the raw-recovery method to find lost files by their contents. Fragmented files have low recovery chances.




Reiser File System
Specifics

Structure: file system header, S+tree.


ReiserFS structure

The file system uses S+-tree which stores files metadata and has descriptors of all files and file fragments. During writing new metadata into the tree, the new tree created for the new data replaces the old one. At the same time, its older copy remains on the disk. Thus, the file system can store lots of metadata copies. This technique is called Copy-on-Write (COW).


File deletion

Procedure: The system updates its S+-tree to exclude a file and renews the map of free space.

Recovery: due to COW, it is possible to recover all files including their names. Moreover, you can also retrieve the previous version of such file from an older S+-tree copy.


Formatting

Procedure: The file system creates new S+-tree over the existing one.

Recovery: COW helps to retrieve the previous file system state enabling complete data recovery possible. However, the chances for complete recovery of lost files decrease, if the file system partition was full. In such case, the system would overwrite the old data with the new one.




XFS file system
Specifics

Structure: complex tree structures, inodes, bitmaps


SGI XFS structure

The XFS file system uses inodes to store files metadata and journaling to keep track of system modifications. Only the metadata is journaled with this file system. Each inode has a header and a bitmap. XFS stores inodes in a special tree in a specific place of the disk. The system also has a bitmap for free storage blocks.


File deletion

Procedure: the inode responsible for this file is excluded from the tree; its place is overwritten with new information.

Recovery: XFS keeps the file metadata still leaving much information and enabling lost files recovery. The chances to recover a deleted file even with a correct file name are quite high.


Formatting

Procedure: root directories of the file system are overwritten.

Recovery: chances to recover the files, which were not in the beginning of the storage, are high. Unlike the files which were close to the disk start.




JFS file system
Specifics

Structure: superblock, B+-tree, journal, i-node file sets


JFS structure

JFS file system employs, B+-tree structure for storing data, journaling for file system modifications and inodes to describe files. The system is also capable of storing several file systems on one partition with links to the same file. File names can be saved in Unicode and UTF8 encodings.


File deletion

Procedure: JFS updates the counter of object uses and releases inode in the inodes map. The directory is rebuilt to reflect changes.

Recovery: A file inode remains on the disk increasing the chances of files recovery up to almost 100%. The recovery chances are low for file names only.


Formatting

Procedure: JFS writes a new tree. It is small from the start and extensible with further file system use.

Recovery: the chances to recover lost files after formatting are quite high due to a small size of a new B+-tree. Moreover, an internal inodes numbering increases chances for an easy files recovery after formatting.